Có 1000 lọ dung dịch trông giống hệt nhau, trong đó đúng 1 lọ có tính axit (làm quỳ tím hóa đỏ). Bạn được nhỏ mỗi lọ lên bao nhiêu mẩu giấy quỳ tùy ý, nhưng chỉ được xem kết quả một lần duy nhất. Cần ít nhất bao nhiêu mẩu giấy quỳ để chắc chắn tìm ra lọ đó?
Gợi ý
Mỗi mẩu giấy cho một câu trả lời có/không, giống như một bit.
Xem đáp án
Đáp án
10 mẩu
Lời giải
Đánh số các lọ từ 0 đến 999 rồi viết sang hệ nhị phân (tối đa 10 chữ số vì 2¹⁰ = 1024 ≥ 1000). Mẩu giấy thứ k nhận một giọt từ mọi lọ có chữ số thứ k bằng 1; các mẩu hóa đỏ ghép lại chính là số hiệu nhị phân của lọ axit.
Câu tiếp: Một lớp học cần có ít nhất bao nhiêu học sinh để xác suất có hai bạn…?