Tổng quan
Câu đố đong nước trở nên nổi tiếng nhờ bộ phim Die Hard with a Vengeance, khi các nhân vật phải tháo bom bằng cách đặt đúng bốn lít lên cân, chỉ dùng bình 5 lít và 3 lít không có vạch chia.
Chỉ với các thao tác đổ đầy, đổ hết và rót, các thể tích đạt được bị chi phối bởi lý thuyết số đơn giản — và bốn lít đạt được vì 5 và 3 không có ước chung.
Cách giải Bài Toán Đong Nước từng bước
- Đổ đầy bình 5 lít (5, 0).
- Rót sang bình 3 lít cho đến khi đầy, còn lại 2 lít (2, 3).
- Đổ hết bình 3 lít (2, 0), rồi rót 2 lít sang nó (0, 2).
- Đổ đầy lại bình 5 lít (5, 2), rồi rót cho đầy bình 3 lít vốn chỉ cần thêm 1 lít — còn đúng 4 lít trong bình lớn (4, 3).
Mấu chốt
Mọi lượng đạt được đều là tổ hợp số nguyên của hai dung tích: 4 = 3 + 3 − 5 + 3, hay đơn giản hơn 4 = 2×5 − 2×3. Vì gcd(5, 3) = 1, bạn có thể đong bất kỳ số lít nguyên nào đến 5.
Biến thể & liên hệ
- Có một lời giải đối xứng đổ đầy bình 3 lít nhiều lần thay vào đó; nó tốn nhiều bước hơn.
- Nói chung bạn chỉ đong được lượng T với hai bình a và b nếu T là bội của gcd(a, b).
- Nếu xem như đồ thị, mỗi cặp (bìnhA, bìnhB) là một nút và tìm kiếm theo chiều rộng tìm ra chuỗi rót ngắn nhất.
Câu hỏi thường gặp
Có thể đong 4 lít trong bình 3 lít không?
Không — bình 3 lít không bao giờ chứa quá 3 lít. 4 lít phải nằm trong bình 5 lít.
Những lượng nào là bất khả?
Với bình 5 và 3 lít, mọi số nguyên từ 0 đến 5 đều đong được vì gcd(5,3)=1. Hai bình 4 và 6 chẳng hạn chỉ đong được các lượng chẵn.