Đố vui : Những túi nào chứa tiền xu giả?

CChắc các bạn biết bài toán này chứ: có 10 cái túi chứa rất nhiều tiền xu, trong đó có 1 túi chứa toàn tiền xu giả, biết rằng mổi đồng xu thật nặng 10g và mỗi dồng xu giả nặng 9g, làm thế nào để 1 lần cân là có thể biết túi nao chứa tiền xu giả. Cũng giả thiết như trên nhưng bài toán của chúng ta khó hơn.

Cũng các giả thiết như trên nhưng trong đó có (1 một nhiều hơn) túi chứa toàn tiền xu giả. cũng lam thế nào để chỉ 1 lần cân là có thể biết túi nào là giả và có bao nhiêu tui giả?

Xem đáp án tham khảo

Cách giải câu đố quen thuộc

  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 đx, “2” lấy 2 đx,…, “10” lấy 10 đx.
  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 tx 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 (còn vì sao thì bà con tự suy nghĩ nhá, cũng khá đơn giản):
  • Nếu ít hơn 10g thì túi chứa tx giả là túi “1”.
  • Nếu ít hơn 20g thì túi chứa tx giả là túi “2”.
  • Nếu ít hơn 30g thì túi chứa tx giả là túi “3”.
  • …v.v…
  • Nếu ít hơn 100g thì túi chứa tx giả là túi “10”.

Lời giải câu đố chính

  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 đx, “1” lấy 2^1 đx,…, “9” lấy 2^9 đx.
  3. Rõ ràng, nếu cả 10 túi đều chứa tx thật thì khối lượng đem cân sẽ là: (2^0+2^2+...+2^9)\times 10=10230g
  4. ôi chỉ nêu cách làm và chứng minh là làm được mà thui hà ^^. 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.

Cách ngắn gọn và mở rộng

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 đx, túi “1” 10^1 đx,…,túi “9” 10^9 đx.
  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.

Nhận xét & chứng minh tổng quát

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 đx, túi “1” b^1 đx,…, túi “9” b^9 đx.
  3. ôi, ta đi đến kq (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à đó 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!
Math2IT

Math2IT

Đây là tác giả chung cho các bài viết không do trực tiếp tác giả cụ thể nào của Math2IT viết. Có thể đó là các bài dịch từ các bài viết nước ngoài hoặc các bài viết thiên về kỹ thuật và thông báo.