Hải Nam

Bài toán cân bi

Có khá nhiều bài toán thú vị xung quanh việc cân để xác định viên bi (đồng tiền) giả có khối lượng khác với đồng tièn thật. Có 2 trường hợp: biết viên bi giả nặng hơn (nhẹ hơn) viên bi thật, hoặc chưa biết. Ta sẽ lần lượt xét các bài toán thuộc 2 trường hợp này.

Biết rõ bi khác loại

Có thời gian tôi sẽ đề cập cụ thể, nhưng nói chung khá đơn giản: khi biết rõ viên bi kia nặng hơn (hay nhẹ hơn) các viên còn lại, thì với n lần cân có thể xác định viên bi giả trong 3ⁿ viên bi.

Không biết bi khác loại

10 viên bi

12 viên bi

http://www.ttvnol.com/toanhoc/107959/trang-5.ttvn

Tui đánh dấu 12 quả cân theo thứ tự từ 1->12.

Lần cân thứ 1: 1,2,3,4 với 5,6,7,8

Lần cân thứ 2: 9,10,11,5 với 1,2,7,8

Ghi chú : xin dùng ký hiệu để biểu diễn kết quả cân:

< : có nghĩa là trọng lượng cân bên trái nhẹ hơn

>: có nghĩa là trọng lượng cân bên trái nặng hơn

=: có nghĩa là trọng lượng hai bên bằng nhau

Trường hợp 1: lần 1 và 2 đều =

=> quả cân giả là quả thứ 12 (quá dễ phải không)
Trường hợp 2: lần 1 = , lần 2 <

=> quả cân giả trong 9,10,11 và quả cân giả nhẹ hơn

=>Lần cân thứ 3:

9 với 10

Nếu < : quả cân giả là quả 9

Nếu > : quả cân giả là quả 10

Nếu = : quả cân giả là quả 11
Trường hợp 3: lần 1 = , lần 2 >

=> quả cân giả trong 9,10,11 và quả cân giả nặng hơn

=>Lần cân thứ 3:

9 với 10

Nếu < : quả cân giả là quả 10

Nếu > : quả cân giả là quả 9

Nếu = : quả cân giả là quả 11
Trường hợp 4: lần 1 < , lần 2 =

=> quả cân giả trong 3,4,6

=>Lần cân thứ 3:

3 với 4

Nếu < : quả cân giả là 3 hoặc 4 và quả cân giả nhẹ hơn => quả cân giả là quả 3

Nếu > : quả cân giả là 3 hoặc 4 và quả cân giả nhẹ hơn => quả cân giả là quả 4

Nếu = : quả cân giả là quả 6
Trường hợp 5: lần 1 > , lần 2 =

=> quả cân giả trong 3,4,6

=>Lần cân thứ 3:

3 với 4

Nếu < : quả cân giả là 3 hoặc 4 và quả cân giả nặng hơn => quả cân giả là quả 4

Nếu > : quả cân giả là 3 hoặc 4 và quả cân giả nặng hơn => quả cân giả là quả 3

Nếu = : quả cân giả là quả 6

13 viên bi

Lấy từ http://www.ttvnol.com/toanhoc/322415.ttvn

Chia 13 viên bi thành 3 phần A, B, C trong đó A và B có 4 viên, C có 5 viên. Cân như sau:

Lần 1: Cân A và B, xét các trường hợp có thể xảy ra:

A = B, khi ấy trong C có viên bi giả, còn A và B đều là thật.

Lại chia C thành hai phần C1 3 viên, C2 2 viên.

Lần 2, đem cân C1 với 3 viên bi thật (lấy từ A), xét các trường hợp:
- Nếu hai bên bằng nhau, suy ra viên còn lại nằm trong C2.
  
  Lần 3: Lấy 1 viên trong C2 đem cân với 1 viên bi thật:
  
  - Nếu hai bên bằng nhau => viên giả la viên còn lại trong C2
  
  - Nếu hai bên không bằng nhau => viên giả là viên của C2 đang được cân (vì viên còn lại đã là thật rồi)
- Nếu hai bên không bằng nhau, có thể giả sử bên C1 nặng hơn, khi đó ta vừa biết được viên giả nằm trong C1, vừa biết được là viên đó nặng hơn viên thật. Đến đây, tách C1 thành 3 viên, lần 3 đem cân hai viên trong chúng:
  
  Nếu hai bên bằng nhau, viên còn lại là viên giả
  
  Nếu hai bên không bằng nhau, khi đó viên nặng hơn là giả.
Nếu A và B không bằng nhau, có thể giả sử A nhẹ hơn B, khi đó 5 viên trong C là thật. Tách A thành hai phần A1 và A2 mỗi bên 2 viên, tách B thành 2 phần B1 3 viên, B2 1 viên. Đánh dấu các viên thuộc A màu xanh, B màu đỏ, đem trộn lẫn A1 và B1.

Lần 2: Cân (A1+B1) với C, xét các trường hợp:
- Nếu hai bên bằng nhau: Khi đó viên giả nằm trong A2 (màu xanh) hoặc B2 (màu đỏ).
  
  Lần 3: Lấy 1 viên xanh (trong A2) cùng với 1 viên đỏ (trong B2), đem cân với hai viên bi thật.
  
  - Nếu hai bên bằng nhau => viên xanh còn lại trong A2 là giả (hơn nữa nó nhẹ hơn viên thật)
  
  - Nếu bên xanh + đỏ nhẹ hơn => viên giả nhẹ hơn viên thật và nằm trong đống xanh+ đỏ. Viên giả nhẹ hơn nên => viên giả nằm trong A => đó là viên xanh đang cân
  
  - Nếu bên xanh + đỏ nặng hơn => viên đỏ là viên giả, lí luận tương tự trên.
- Nếu hai bên không bằng nhau: Khi đó viên giả nằm trong A1 + B1. Ta xét các trường hợp:
  
  - Nếu (A1+B1) nặng hơn => viên giả nặng hơn viên thật và nằm trong A1+B1. Viên giả nặng hơn nên => viên giả nằm trong B => viên giả nằm trong B1 ( 1 trong 3 viên đỏ)
  
  Lần 3: Đem cân hai viên của B1:
  
  Nếu bằng nhau => viên còn lại là giả
  
  Nếu không bằng nhau, khi đó bên nặng hơn sẽ chứa viên giả.
  
  - Nếu (A1+B1) nhẹ hơn => viên giả nhẹ hơn viên thật và nằm trong A1+B1. Viên giả nhẹ hơn nên => viên giả nằm trong A => viên giả nằm trong A1 ( 1 trong 2 viên xanh)
  
  Lần 3: Đem cân hai viên của A1 với nhau, bên nào nhẹ hơn là bên giả.

13 viên bi (cách 2)

Đây là cách của bạn Cuong_DC9 gửi ở Diễn đàn tin học

Ta đánh số các đồng tiền từ 1 đến 13, lần cân thứ nhất: 1 2 3 4 với 5 6 7 8

Nếu cân thăng bằng, đồng giả sẽ nằm trong số 9 10 11 12 13, lần cân thứ 2: 1 2 3 với 9 10 11
1. nếu thăng bằng, , đồng giả sẽ nằm trong số 12 13, lần cân thứ 3: 1 với 12
2. nếu < , đồng giả nằm trong số 9 10 11 và nhẹ hơn đồng thật, lần cân thứ 3: 9 với 10
  
  - nếu thăng bằng, , đồng giả là 11
  
  - nếu không thăng bằng, , đồng giả nằm trên đĩa cao hơn vì nhẹ hơn
3. nếu > , đồng giả nằm trong số 9 10 11 và nặng hơn đồng thật, lần cân thứ 3: 9 với 10
  
  - nếu thăng bằng, , đồng giả là 11
  
  - nếu không thăng bằng, , đồng giả nằm trên đĩa thấp hơn vì nặng hơn
Nếu < , lần cân thứ 2: 4 5 6 7 với 8 9 10 11
1. nếu thăng bằng, , đồng giả sẽ nằm trong số 1 2 3 và nhẹ hơn đồng thật, lần cân thứ 3: 1 với 2,
  
  - nếu thăng bằng, , đồng giả là 3
  
  - nếu không thăng bằng, , đồng giả nằm trên đĩa cao hơn vì nhẹ hơn
2. nếu < , đồng giả nằm trong số 4 hoặc 8 vì ta để nguyên trên điã cân 2 đồng này , lần cân thứ 3: 4 với 9
  
  - nếu thăng bằng, , đồng giả là 8
  
  - nếu không thăng bằng, , đồng giả là 4
3. nếu > , đồng giả sẽ nằm trong số 5 6 7 và nặng hơn đồng thật, lần cân thứ 3: 5 với 6,
  
  - nếu thăng bằng, , đồng giả là 7
  
  - nếu không thăng bằng, , đồng giả nằm trên đĩa thấp hơn vì nặng hơn
Nếu > , phương pháp giải tương tự khả năng 2.

Trường hợp tổng quát

Báo Tin học và Nhà trường (năm 2000)

Hơn nửa thế kỷ trước, có một bài toán đã lôi cuốn sự chú ý của nhiều nhà toán học, nhất là ở Anh và Mỹ. Nội dung bài toán như sau:

Có m >= 3 đồng tiền có bề ngoài giống hệt nhau. Tất cả các đồng tiền có khối lượng như nhau, ngoại trừ một đồng tiền giả có khối lượng khác các đồng tiền thật, nhưng cũng không biết kiểu của nó (nặng hơn hay nhẹ hơn các đồng tiền thật). Chỉ bằng một chiếc cân thăng bằng (2 đĩa) không có quả cân bạn hãy tìm ra đồng tiền giả và xác định kiểu của nó với số lần cân ít nhất.

Năm 1945, một lời giải của bài toán được đăng trên "The Mathematical Gazette" của Anh. Tác giả bài báo là Gudstein R.L, sau này đã trở thành một chuyên gia nổi tiếng trong ngành logic toán học. Ông đã chỉ ra rằng, với n lần cân có thể xác định được đồng tiền giả từ m đồng tiền với $n~\le~\Large\frac{3^n-2n+3}2$ . Tuy nhiên lời giải của Gudstein đã không phải là tốt nhất. Thực ra với n lần cân ta có thể xác định được đồng tiền giả từ m đồng tiền với $n~\le~\Large\frac{3^n-3}2$ . Nhiều nhà toán học đã phát hiện ra điều này ngay sau đó, nên đến năm 1946, tạp chí trên đã cho đăng một danh sách dài các nhà toán học cùng kết quả của họ và kết quả được coi là tốt nhất của Daison F.J, người mà sau này cũng đã trở thành một nhà vật lý nổi tiếng.

Cho dù về sau, đã có nhiều lời giải khác của bài toán này được đăng tải nhưng những ý tưởng mà Daison sử dụng trong lời giải của mình vẫn không bị quên lãng vì tính độc đáo của chúng. Lời giải của ông dựa trên hệ tam phân (hệ đếm cơ số 3), cách đánh số các đồng tiền và cách chọn các đồng tiền cho một lần cân hoàn toàn không phụ thuộc vào kết quả của lần cân trước đó.