Chai Rượu Độc

Nếu dùng một nô lệ để thử lần lượt từng chai, nhà vua sẽ mất 1000 ngày (trong trường hợp xấu nhất) để tìm ra chai rượu độc.

Nếu dùng 1000 nô lệ, mỗi người thử một chai thì sau một ngày nhà vua sẽ tìm ra chai rượu độc.

Hai cách trên, hoặc là tốn thời gian, hoặc là phải dùng nhiều nô lệ. Phương pháp sau dựa trên hệ số nhị phân và chỉ dùng 10 nô lệ để xác định chai rượu độc trong đúng một ngày.

Đánh số chai rượu từ 1 tới 1000 và nô lệ từ 1 tới 10. Nô lệ thứ i uống một phần nhỏ của chai rượu k (k = 1 -> 1000), nếu bit thứ i trong biểu diễn nhị phân của k là 1. Ví dụ, nô lệ thứ nhất uống một phần nhỏ của chai rượu 1, 3, 5, …, 999. Những nô lệ nào chết thì đó chính là biểu diễn nhị phân của chai rượu có độc. Ví dụ nếu nô lệ thứ 1, 2, 5, 10 bị chết thì chai rượu độc là chai \(1000010011_2=531\).