Tổng quan
Câu đố rượu độc là bài học sống động về mã hóa nhị phân: một nhúm người nếm có thể tìm ra một chai độc trong số lượng chai tăng theo cấp mũ.
Cách giải Chai Rượu Độc từng bước
- Đánh số các chai theo nhị phân và gán mỗi người nếm cho một bit.
- Người nếm uống từ mọi chai có bit tại vị trí của họ bằng 1.
- Tập những người nếm phát bệnh ghép thành số chai độc dưới dạng nhị phân.
Mấu chốt
Mỗi người nếm trả lời một câu có/không — một bit. Với b bit độc lập, bạn gọi tên được bất kỳ chai nào trong 2^b chai, nên số người nếm tăng theo logarit.
Biến thể & liên hệ
- Phiên bản nổi tiếng có 1000 chai giải được chỉ với 10 người nếm (2¹⁰ = 1024).
- Cùng cách mã hóa làm nền cho mã Hamming và tính chẵn lẻ RAID.
Câu hỏi thường gặp
Nếu hai chai bị độc thì sao?
Cách gán nhị phân đơn giản không còn đủ; bạn cần thêm người nếm và một mã phức tạp hơn.