Tổng quan
Câu đố đồng xu giả là món quen thuộc của toán học giải trí. Bạn có một bộ đồng xu trông giống hệt nhau, đúng một đồng sai trọng lượng, và một cân hai đĩa chỉ cho biết bên nào nặng hơn — chứ không cho biết nặng hơn bao nhiêu.
Mấu chốt là mỗi lần cân có ba kết quả khả dĩ — trái nặng hơn, phải nặng hơn, hoặc cân bằng — nên một lần cân có thể chia các nghi phạm thành ba nhóm cùng lúc.
Cách giải Đồng Xu Giả từng bước
- Chia 8 đồng xu thành ba nhóm: 3, 3 và 2.
- Cân hai nhóm ba đồng với nhau.
- Nếu một bên nặng hơn, đồng giả nằm trong ba đồng đó; nếu cân bằng, nó nằm trong nhóm hai đồng để riêng.
- Lần cân thứ hai: lấy hai nghi phạm cân với nhau. Đồng nặng hơn là đồng giả — hoặc nếu cân bằng, đồng chưa cân là đồng giả.
Mấu chốt
Vì mỗi lần cân có ba kết quả, k lần cân có thể phân biệt 3^k trường hợp. Hai lần cân bao quát tới 9 đồng — nên 8 đồng giải được thoải mái, và đó là lý do bạn chia cho ba, không phải hai.
Biến thể & liên hệ
- Phiên bản khó kinh điển có 12 đồng mà bạn thậm chí không biết đồng giả nặng hơn hay nhẹ hơn — vẫn giải được trong ba lần cân.
- Ý tưởng 'chia làm ba' chính là tìm kiếm tam phân, người anh em hệ cơ số 3 của tìm kiếm nhị phân.
- Lý thuyết thông tin đặt ra giới hạn: bạn cần ít nhất ⌈log₃(số trường hợp)⌉ lần cân.
Câu hỏi thường gặp
Vì sao chia ba nhóm, không phải hai?
Vì cân cho ba kết quả, chia ba tận dụng tối đa mỗi lần cân — chia đôi sẽ lãng phí kết quả 'cân bằng'.
Có thể làm 9 đồng trong hai lần cân không?
Được. Vì 3² = 9, chín đồng đúng là số tối đa giải được trong hai lần cân khi bạn biết đồng giả nặng hơn.