Puzzle 101: Những túi nào chứa tiền xu giả?

1. Đánh số lần lượt các túi đựng đồng xu là “1”, “2”,…,”10″.
2. Lấy lần lượt từ các túi đó: “1” lấy 1 đồng xu , “2” lấy 2 đồng xu ,…, “10” lấy 10 đồng xu .
3. Rõ ràng nếu cả 10 túi đều chứa toàn tiền xu thật thì khối lượng đem cân sẽ là 550g.
4. Nhưng ở đây do có 1 túi chứa toàn đồng xu giả nên khối lượng đem cân sẽ ít hơn 550g, và nếu ít hơn bao nhiêu thì ta sẽ biết là túi nào (bạn có thể tự suy luận tiếp):
   • Nếu ít hơn 10g thì túi chứa đồng xu giả là túi “1”.
   • Nếu ít hơn 20g thì túi chứa đồng xu giả là túi “2”.
   • Nếu ít hơn 30g thì túi chứa đồng xu giả là túi “3”.
   • …v.v…
   • Nếu ít hơn 100g thì túi chứa đồng xu giả là túi “10”.

1. Đánh số các túi đựng đồng xu lần lượt là “0”, “1”, …, “9”.
2. Lấy lần lượt từ các túi đó: “0” lấy $2^0$ đồng xu, “1” lấy $2^1$ đồng xu,…, “9” lấy $2^9$ đồng xu .
3. Rõ ràng, nếu cả 10 túi đều chứa đồng xu thật thì khối lượng đem cân sẽ là: $(2^0+2^2+…+2^9)\times 10=10230$g
4. Tôi chỉ nêu cách làm và chứng minh là làm được mà thôi. Cái này lập trình chắc ko lâu…

Bây giờ ta chứng minh cách tìm các túi từ a là duy nhất (chứng minh bằng phản chứng):

• $a=2^x+…+2^y$ (với $2^x,…,2^y$ là nhóm số thứ nhất tương ứng với nhóm túi thứ nhất)
• Gỉa sử còn 1 nhóm số khác $2^u,…,2^v$ cũng có tổng bằng a.
• Suy ra: $2^x+…+2^y=2^u+…2^v$, rõ ràng ko mất tính tổng quát, ta có thể giả sử ko có bất kì 2 phần tử nào thuộc 2 nhóm số trên là giống nhau (vì nếu giống là ta đã triệt tiêu 2 bên dấu bằng òi, đúng hong ^^).
• Và chú ý là ko có phần tử nào là $2^0$ cả, vì nếu có thì 1 trong 2 vế của đẳng thức sẽ là $1+…=$ số lẻ, vế còn lại tất nhiên là số chẵn $ \Rightarrow $ vô lý.
• Thực hiện phép đặt nhân tử chung, ta có: $2^k(1+…+)=2^i(1+…+)$.
• , khi đó đẳng thức thành: $2^k(1+…+)=2^k.2^h(1+…+)$, với $i=k+h$, tới đây, chắc các bạn cũng thấy sự vô lí khi triệt tiêu $2^k$ của 2 bên.

Vậy là đã chứng minh xong, vấn đề bây giờ là tìm ra nhóm số đó $ \Rightarrow $ các túi thiếu, tất nhiên là làm được tuy hơi mệt.

Về cơ sở thì 2 cách khá giống nhau nhưng cách sau này tương đối dễ thở hơn. Cách đó như sau:

1. Lấy túi “0” $10^0$ đồng xu , túi “1” $10^1$ đồng xu ,…,túi “9” $10^9$ đồng xu .
2. Suy ra nếu khối lượng giảm b (gam), thì trong b đó có bao nhiêu chữ số 1 thì bấy nhiêu túi thiếu, và vị trí số 1 chính là vị trí của túi thiếu.

Thay vì 2 và 10 như trên, ta có thể chứng minh đó là 1 số b bất kì ((b ne 1)).

1. Đánh số túi y chang trên.
2. Lấy từ “0” $b^0$ đồng xu , túi “1” $b^1$ đồng xu ,…, túi “9” $b^9$ đồng xu .
3. ôi, ta đi đến kết quả (sau khi đặt nhân tử chung): $b^k(1+…+)=b^i(1+…+)$ (*)
4. Ở đây, (*) có thể có k hay i bằng 0 cũng được nhưng chỉ có 1 trong 2 giá trị đó mà thôi. Nhưng ta nhận thấy rằng dù giá trị nào thì 1 vế của (*) sẽ chia cho b dư 1, còn về kia chia hết cho b, suy ra vô lí.
5. Vậy ta chỉ có thể tìm được duy nhất 1 bộ số $b^x,…,b^y$ nào đó thỏa $a=b^x+…+b^y$

Các bạn tưởng cái trên đã là tổng quát? Chưa đâu, vẫn còn cách tổng quát hơn, từ cách này, ta thấy bài toán có rất nhiều cách làm, vì thế tìm ra 1 trong các cách ko có gì là đặc biệt.

1. Ta đánh số túi là “1”,”2″,…,”9″.
2. Lấy từ túi “1” đến túi “9” số lượng đồng xu lần lượt là: $a_1,a_2,…,a_9$.
3. Chỉ cần chọn sao cho ${a_i} > \sum\limits_{k = 1}^{i – 1} {{a_k}} $ là ok. Nghĩa là chỉ cần chọn sau cho số sau lớn hơn tổng tất cả các số trước.
4. Còn việc chứng minh thì cũng ko quá khó, các bạn tự suy nghĩ nha!