Bài toán thuốc độc - suy luận nhị phân?

Bài toán 1: Bài toán thuốc độc - suy luận nhị phân?

Một nhà khoa học có 7 chai thuốc, trong đó có đúng 1 chai thuốc độc. Chất độc sẽ giết chết bất kỳ sinh vật nào uống phải trong vòng 1 giờ. Cần tối thiểu bao nhiêu con chuột thí nghiệm để nhà khoa học tìm ra chai thuốc độc trong đúng 1 giờ (thời gian cho con chuột thí nghiệm thử thuốc là không đáng kể)?

Đây là một bài toán suy luận nhị phân cổ điển, tương tự bài “chuột thử rượu độc”. Hướng giải rất thông minh và sử dụng hệ nhị phân để mã hóa thông tin, từ đó tìm ra chai độc với số lượng chuột tối thiểu.

---

📌 Đề bài tóm tắt:

• Có 7 chai thuốc, chỉ 1 chai chứa độc.

• Nếu một con chuột uống thuốc độc, nó sẽ chết sau 1 giờ.

• Mục tiêu: xác định đúng chai độc trong 1 giờ, sử dụng ít chuột nhất.

---

🧠 Ý tưởng giải:

Thay vì mỗi con chuột thử từng chai, ta gộp thuốc lại và gán mã nhị phân cho từng chai. Sau đó, mỗi chuột sẽ uống thuốc theo từng bit của mã.

📍 Bước 1: Mã hóa 7 chai thuốc bằng nhị phân

Số lượng chai = 7 ⇒ cần phân biệt 7 trạng thái khác nhau

• Số lượng bit nhị phân cần tối thiểu để phân biệt 7 chai là:

  $$\text{ bit}$$

→ Ta cần 3 con chuột

---

📍 Bước 2: Gán mã nhị phân cho từng chai thuốc

📍 Bước 3: Giao thuốc cho chuột

• Gọi 3 chuột là A, B, C, mỗi chuột tương ứng với 1 bit (bit thứ nhất, thứ hai, thứ ba).

• Nếu bit nào là 1 → chuột đó uống thuốc từ chai tương ứng.

Ví dụ:

• Chai 5 là 101 → chuột A và C uống thuốc từ chai 5

• Chai 3 là 011 → chuột B và C uống thuốc từ chai 3

Sau khi chuột uống xong, chờ 1 giờ và quan sát con nào chết:

• Ví dụ, nếu chuột A và C chết → mã nhị phân chết là 101 ⇒ chai số 5 là độc.

• Nếu chỉ chuột B chết → mã chết là 010 ⇒ chai số 2 là độc.

---

✅ Kết luận:

Cần tối thiểu 3 con chuột để tìm ra chai thuốc độc trong vòng 1 giờ.

(Đây là cách tối ưu nhất, vì 2 con chuột chỉ phân biệt được tối đa 2^2 = 4 trạng thái < 7.)

====

Bài toán 2: Phần A. Có 1000 chai thuốc, chỉ 1 chai độc

❓ Hỏi: Cần tối thiểu bao nhiêu con chuột để xác định chai độc duy nhất trong vòng 1 giờ?

🔍 Hướng giải:

• Cần phân biệt 1000 trạng thái khác nhau ⇒ tương ứng với số nhị phân từ 0 đến 999.

• Tối thiểu số chuột cần:

  ⌈log⁡21000⌉=⌈9.97⌉=10

✅ Trả lời: Cần tối thiểu 10 con chuột để xác định chai độc duy nhất trong 1000 chai thuốc (với 1 giờ thử nghiệm).

Bài toán 3: Có 1000 chai thuốc, nhưng có nhiều hơn 1 chai độc

❓ Ví dụ: Có 2 chai độc, hỏi cần tối thiểu bao nhiêu con chuột?

🔍 Phân tích:

Nếu có 2 chai độc, ta cần tìm ra cặp vị trí nào trong 1000 chai là độc.

• Số lượng trường hợp có 2 chai độc:

  (1000C2)=1000⋅999/2=499,500 tổ hợp

• Vậy cần phân biệt 499.500 trạng thái → cần số chuột tối thiểu là:

  ⌈log⁡2(499,500)⌉=⌈18.9⌉=19

✅ Trả lời: Cần tối thiểu 19 con chuột để xác định chính xác 2 chai thuốc độc trong 1000 chai, trong 1 giờ.

---

🧠 Tổng quát:

---

🎯 Lưu ý:

• Cách làm luôn là gán mã nhị phân, kết hợp theo tổ hợp nếu có nhiều hơn 1 chai độc.

• Tất cả chuột uống cùng lúc, quan sát tổ hợp chuột chết sau 1 giờ là đủ xác định.