Của chúng tôi bộ câu đố gần đây nổi bật với thang cân bằng hai đĩa khiêm tốn, trong lịch sử là biểu tượng của thương mại và chính phủ, nghệ thuật và khoa học. Thang cân bằng cũng phổ biến trong toán học giải trí. Các câu đố về cân bằng đòi hỏi phải suy luận rõ ràng, hợp lý và phù hợp với khả năng khái quát hóa toán học. Hãy xem làm thế nào Quanta độc giả đã cân bằng những phẩm chất này trong các câu đố dưới đây.
Câu đố 1
Bạn có tám đồng xu trông giống hệt nhau. Một là giả và nhẹ hơn những cái khác, có trọng lượng giống hệt nhau. Tìm đồng xu xấu trong hai lần cân. Tìm công thức chung cho số đồng xu tối đa mà bạn có thể tìm thấy đồng xu giả trong x cân nặng.
Giải quyết một phiên bản đơn giản của một vấn đề thường tiết lộ chìa khóa cho giải pháp. Trong trường hợp này, hãy tưởng tượng rằng bạn chỉ có ba đồng xu, trong đó một đồng nhẹ hơn hai đồng còn lại. Nếu bạn cân bất kỳ một trong số chúng với một trong hai cái còn lại, chúng sẽ cân bằng hoặc không. Nếu không, bạn biết cái nào nhẹ hơn. Nếu chúng cân bằng, thì cái thứ ba là cái nhẹ. Bạn chỉ cần một lần cân duy nhất.
Vì vậy, trong câu đố này, nếu bạn có thể tách riêng một nhóm ba người (hoặc ít hơn) có chứa đồng xu nhẹ trong lần cân đầu tiên, thì bạn sẽ chỉ cần thêm một lần cân nữa. Bạn có thể làm điều này bằng cách cân bằng ba bất kỳ với ba bất kỳ khác. Nếu hai nhóm không cân bằng, bạn đã tìm thấy nhóm chứa vật nhẹ và có thể tiến hành như trên cho lần cân thứ hai. Nếu chúng cân bằng, chỉ cần đem hai đồng xu còn lại so sánh với nhau, bạn sẽ tìm được đồng xu nhẹ.
Lưu ý rằng điều này cũng hoạt động nếu có ba đồng xu trong nhóm không cân, vì vậy chúng ta có thể bắt đầu với chín đồng xu. Theo logic này và bắt đầu với ba đồng xu, cứ mỗi lần cân thêm, chúng ta có thể tìm thấy đồng xu nhẹ gấp ba lần số đồng xu mà chúng ta có trước đó. Công thức cho chúng ta số xu tối đa n in w cân là do đó n = 3w.
Câu đố 2
Bạn có 12 đồng xu trông giống hệt nhau. Một cái nặng hơn hoặc nhẹ hơn những cái khác, có trọng lượng giống hệt nhau.
-
Tìm đồng xu xấu trong ba lần cân.
-
Số lượng đồng xu tối đa mà bạn có thể tìm thấy đồng xấu trong bốn lần cân là bao nhiêu? Mô tả cách bạn sẽ tìm thấy đồng xu giả.
Giải pháp cho câu đố này đã được mô tả tốt bởi Trở cỏ để phơi khô, người cũng đã chỉ ra rằng bạn thực sự có thể phát hiện ra đồng xu xấu trong số 13 đồng xu trong ba lần cân. Đây là giải pháp của Ted (với các vết lõm để phân tách ba lần cân trong mỗi trường hợp):
Bắt đầu bằng cách cân 4 đồng xu so với 4 đồng xu.
Trường hợp 1: Nếu không cân, trong lần cân thứ hai, đặt 2 mỗi bên nặng hơn lên cả hai bên của cân cùng với 1 mỗi bên nhẹ hơn.
1a: Nếu không cân bằng, đồng xu xấu là 2 đồng xu vẫn ở bên nặng hoặc một đồng xu vẫn ở bên nhẹ.
Cân 2 đồng xu nặng có thể, đồng xấu là đồng nặng hơn trong hai đồng hoặc đồng nhẹ nếu chúng cân bằng.
1b: Nếu lần cân thứ hai cân bằng, đồng xấu là một trong 2 đồng không được sử dụng từ phía nhẹ hơn của lần cân thứ nhất.
Cân chúng với nhau, cái nhẹ hơn là xấu.
Trường hợp 2: Nếu cân bằng, đồng xấu là 5 trong 3 đồng còn lại. Cân 3 trong số đó so với XNUMX bất kỳ đã được cân (được biết là [tốt]).
Trường hợp 2a: Nếu không cân thì biết đồng xu xấu là 3 trong XNUMX đồng đó và nặng hay nhẹ.
Lần cân thứ ba là bất kỳ 2 trong số đó so với nhau - nếu không cân bằng, xác định đồng xu xấu, nếu cân bằng thì đó là lần cân cuối cùng trong ba lần.
Trường hợp 2b: Nếu lần cân thứ 2 cân thì đồng xấu là XNUMX trong XNUMX đồng còn lại.
Cân một trong số chúng với một đồng xu tốt đã biết. Nếu kết quả này không cân bằng, đồng xu mới này là xấu và bạn biết nó nặng hay nhẹ. Nếu kết quả này cân bằng thì đồng thứ 13 là xấu, nhưng chưa biết nặng hay nhẹ (cái này ta không cần biết, thế là xong).
Trở cỏ để phơi khô cũng tiếp tục chỉ ra rằng số lượng đồng xu tối đa cho bốn lần cân là 40. Công thức của câu đố này là: n = (3w − 1)/2.
Đối với các câu đố còn lại, các công thức tổng quát vẫn đang được các nhà toán học chuyên nghiệp nghiên cứu và là chủ đề của các bài báo đã xuất bản, một số trong đó đã được trích dẫn bởi Rainer aus dem Mùa xuân. Tôi sẽ giới hạn bản thân trong các giải pháp cho số lượng nhỏ đồng xu mà chúng tôi xem xét trong các câu đố và sẽ chỉ đề cập đến những khái quát hóa tuân theo tự nhiên từ các phương pháp được sử dụng trong những trường hợp này.
Câu đố 3
Đây là một biến thể của câu đố 1. Bạn lại có tám đồng xu trông giống hệt nhau, một trong số đó nhẹ hơn những đồng xu khác. Tuy nhiên, bây giờ bạn có ba thang đo. Hai trong số các thang đo hoạt động, nhưng thang đo thứ ba bị hỏng và cho kết quả ngẫu nhiên (đôi khi đúng và đôi khi sai). Bạn không biết cân nào bị hỏng. Cần bao nhiêu lần cân để tìm ra đồng xu nhẹ?
Như chúng ta đã thấy trong vấn đề 1, điều này chỉ cần hai lần cân với sự cân bằng tốt. Ta cũng biết hai chiếc cân tốt sẽ luôn đồng nhất nên chỉ cần lặp lại mỗi lần cân trên cả ba chiếc cân thì sẽ có đáp số trong sáu lần cân như bạn đọc gợi ý. Nếu chúng ta cố gắng thực hiện với số lần cân ít hơn, thì sẽ hơi phức tạp một chút. Chúng ta không thể xác định một chiếc cân tốt chỉ bằng cách cân cùng một đồng xu trên hai chiếc cân, bởi vì ngay cả khi chúng đồng ý, một trong hai chiếc cân vẫn có thể là chiếc cân xấu. (Điều này cũng cho thấy thông tin sai lệch hoặc thông tin ngẫu nhiên có thể làm sai lệch sự thật dễ dàng như thế nào.)
Trên thực tế, vấn đề này có thể được giải quyết, rất thông minh, chỉ trong bốn lần cân! Rainer aus dem Mùa xuân đã đăng giải pháp bằng cách sử dụng một ký hiệu mới dường như đã được tạo cho câu đố này. Nhưng trước khi bạn đến đó, tôi muốn bạn tưởng tượng một kịch bản mà tôi hy vọng sẽ khiến mọi thứ trở nên trực quan hơn.
Hãy tưởng tượng bạn là một thám tử đang điều tra một vụ gây tai nạn rồi bỏ trốn ở một quốc gia nhỏ bé có biển số xe hai chữ số chỉ sử dụng các chữ số 0, 1 và 2. Ba người A, B và C đã quan sát vụ việc. Hai trong số họ luôn trả lời đúng câu hỏi có ba lựa chọn và một người đưa ra câu trả lời hoàn toàn ngẫu nhiên. Bạn không biết ai là người trả lời ngẫu nhiên. Bạn phải hỏi mỗi người trong số họ một câu hỏi có ba lựa chọn và sau đó chọn người chắc chắn đang nói sự thật để có thêm thông tin.
Đây là cách bạn làm điều đó. Hỏi A nếu chữ số đầu tiên là 0, 1 hoặc 2. Giả sử A nói 2. Hỏi B nếu chữ số thứ hai là 0, 1 hoặc 2. Giả sử B nói 1. Sau đó, yêu cầu C đưa ra lựa chọn giữa ba câu sau:
- Chỉ có A là nói sự thật.
- Chỉ có B là nói sự thật.
- Cả hai đều đang nói sự thật.
Bạn có thể tin vào chữ số mà C nói với bạn và hỏi người đó về chữ số kia. Để hiểu tại sao, hãy xem xét rằng nếu A nói dối, thì C đáng tin cậy và sẽ nói rằng B đang nói thật. Trên thực tế, chữ số thứ hai sẽ là 1 và sau đó bạn có thể đặt câu hỏi cho B về chữ số đầu tiên. Tương tự, nếu B nói dối, thì C lại đáng tin cậy và sẽ nói rằng A đang nói thật. Sau đó, chữ số đầu tiên thực tế là 2 và bạn có thể hỏi A về chữ số thứ hai. Cuối cùng, nếu C nói dối, thì cả A và B đều đáng tin cậy, vì vậy bạn vẫn có thể tin và chọn bất kỳ ai mà C nói. (Và nếu C nói rằng cả A và B đều nói thật, thì cả hai đều phải như vậy.) Mấu chốt ở đây là sự lựa chọn câu hỏi của bạn không cho phép C nói dối theo cách khiến cả A và B phải nghi ngờ. Vì ít nhất một trong A và B phải đáng tin cậy, bạn luôn có thể chọn câu mà C đồng ý, ngay cả khi đó chỉ là câu trả lời ngẫu nhiên. Nếu cả ba đều đồng ý thì bạn đã có cả hai chữ số của biển số xe.
Đây là cách dịch câu chuyện này trở lại câu đố của chúng tôi. Tỷ lệ là A, B và C. Bạn có thể dịch hai chữ số của biển số sang đồng xu như sau: 01 là đồng xu 1, 02 là đồng xu 2, 10 là đồng xu 3, 11 là đồng xu 4, 12 là đồng xu 5, 20 là đồng xu 6, 21 là đồng xu 7 và 22 là đồng xu 8. Những độc giả tinh ý sẽ nhận ra rằng đây là hệ thống số cơ số 3 (hoặc bộ ba). Cũng lưu ý rằng có thể có thêm một số 00, mà bạn có thể sử dụng cho đồng xu thứ chín mà kỹ thuật này cũng sẽ hoạt động, như trong câu đố 1.
Đối với lần cân đầu tiên, bạn chia đồng xu cho chữ số đầu tiên (cơ số 3), vì vậy ba nhóm của bạn sẽ là đồng xu [1, 2], [3, 4, 5] và [6, 7, 8]. Cân [3, 4, 5] so với [6, 7, 8] trên thang A. Nếu A hoạt động tốt, bạn sẽ có nhóm chữ số đầu tiên chính xác như trong câu đố 1. Tương tự, đối với lần cân thứ hai trên thang B, các nhóm của bạn sẽ là những số có cùng chữ số thứ hai: [1, 4, 7], [2, 5, 8] và [3, 6]. Nếu B hoạt động tốt, bạn sẽ có chữ số thứ hai chính xác. Đối với lần cân thứ ba, trên thang C, bạn cân nhóm mà A đã xác định so với nhóm mà B đã xác định. Theo ví dụ của chúng tôi, đối với 21, các nhóm sẽ là [6, 7, 8] và [1, 4, 7]. Đồng xu 7 không thể được đặt ở cả hai bên cùng một lúc, vì vậy chúng tôi bỏ nó ra và cân [6, 8] và [1, 4] với nhau. Lưu ý rằng nếu cả A và B đều đáng tin cậy, thì trên thực tế, 7 là câu trả lời đúng và việc bên nào nhẹ hơn ở C không quan trọng. Nếu tình cờ cân trên C cân bằng, thì cả ba cân đều đồng ý và bạn có câu trả lời của mình (đồng xu 7) chỉ sau ba lần cân. Nếu A đáng tin cậy và B thì không, đồng xu nhẹ hơn nằm trong [6, 8], thang đo C sẽ xác nhận và nếu B đáng tin cậy còn A thì không, thì đồng xu nhẹ hơn nằm trong [1, 4], thang đo C cũng sẽ xác nhận.
Vì vậy, trong ba lần cân, chúng tôi đã xác định được đồng xu nhẹ hoặc thu hẹp nó thành một nhóm hai đồng xu và chúng tôi cũng đã xác định được một thang đo hoạt động. Lần cân thứ tư trên thang A hoặc thang B (bất kỳ thang C nào đồng ý) sẽ thực hiện phần còn lại.
Giải pháp này gây ấn tượng với tôi là đẹp một cách đáng kinh ngạc!
Phương pháp này có thể được khái quát hóa để tìm đồng xu nhẹ trong số 32x xu trong 3x + 1 quả cân với bộ đĩa cân đã cho sẵn. Vì vậy, bạn cần bảy lần cân cho 81 đồng xu. Đối với số lượng xu lớn hơn (>~1,000), một giải pháp thậm chí còn mạnh mẽ hơn tồn tại.
Câu đố 4
Bạn có 16 đồng xu, trong đó có XNUMX đồng nặng và có trọng lượng như nhau. Tám cái còn lại nhẹ và có cùng trọng lượng. Bạn không biết đồng xu nào nặng hay nhẹ. Các đồng xu trông giống hệt nhau ngoại trừ một đồng xu có dấu hiệu đặc biệt. Với một chiếc cân tốt, bạn có thể biết đồng xu đặc biệt nhẹ hay nặng trong ba lần cân không? Số xu tối đa mà bạn có thể bắt đầu và giải thành công bài toán này trong bốn lần cân là bao nhiêu?
Thoạt nhìn, câu đố này gần như không thể giải được trong ba lần cân, như một độc giả của chúng tôi đã kết luận. Tuy nhiên, với một số thông minh nó có thể được thực hiện, và cả hai Trở cỏ để phơi khô và Rainer aus dem Mùa xuân đã đưa ra các giải pháp chính xác. Ted đã cung cấp một số nguyên tắc chung vô giá đáng được chú ý.
Đầu tiên, cho đến khi bạn nhận được kết quả không cân bằng khi cân, bạn sẽ không có đủ thông tin để xác định xem đồng xu đặc biệt nặng hay nhẹ. Vì vậy, bạn phải cố gắng và ép buộc một kết quả không cân bằng.
Thứ hai, nếu bạn nhận được kết quả cân bằng (chẳng hạn đồng xu đặc biệt A cân bằng đồng xu B), bạn có thể kết hợp các đồng xu đã cân bằng và cân chúng với hai đồng xu khác, C và D. Nếu chúng không cân bằng, bạn có câu trả lời; nếu không, bây giờ bạn đã nhân đôi số lượng đồng xu tương tự, điều này có thể giúp bạn có được câu trả lời không cân bằng trong lần cân tiếp theo. Bạn cũng có thể thực hiện quá trình này ngược lại với số đồng xu là lũy thừa của hai (4, 8, v.v.) nếu bạn có kết quả ban đầu không cân bằng như trong giải pháp sau.
Dưới đây là toàn bộ quy trình có thể xác định loại đồng xu đặc biệt A trong mọi trường hợp trong ba lần cân. (B, C và D là ba đồng xu được đặt cùng phía với A khi cân 1 (W1); X và Y là hai đồng xu không được sử dụng trong W1.)
Câu đố này được phát minh bởi nhà toán học người Nga Konstantin Knop, một cơ quan có thẩm quyền trên thế giới về các câu đố cân bằng đồng xu. Nhiều bài báo của anh ấy bằng tiếng Nga, nhưng bạn có thể tìm thấy một số câu đố về đồng xu (trong số những câu đố thú vị khác) trên Blog của chúng tôi. của cộng tác viên Tanya Khovanova.
Để khái quát hóa, tôi sẽ để bạn xem liệu phương pháp tương tự này có hiệu quả với việc tìm ra loại đồng xu đặc biệt trong số 32 đồng xu, trong đó có 16 đồng nặng và 16 đồng nhẹ.
Câu đố 5
Bạn có n những đồng tiền trông giống hệt nhau, một số là giả và nhẹ hơn những đồng khác. Tất cả những gì bạn biết là có ít nhất một đồng xu giả và có nhiều đồng xu bình thường hơn đồng xu giả. Công việc của bạn là phát hiện tất cả các đồng tiền giả.
Thực tế là có ít nhất một đồng xu nhẹ và có nhiều đồng xu bình thường hơn đồng xu nhẹ làm cho câu đố này ít phức tạp hơn so với lần đầu xuất hiện, ít nhất là đối với số lượng nhỏ. Hãy xem số lần cân từ một đến tám đồng xu.
Đối với một và hai đồng xu, không thể có đồng xu nhẹ theo điều kiện thứ hai, vì vậy không cần cân.
Ba đồng xu: Chỉ một đồng xu nhẹ. Yêu cầu một quả cân cho mỗi câu đố 1.
Bốn xu: Chỉ một đồng xu nhẹ. Cần thêm một lần cân, vì vậy w = 2.
Ngũ xu: Một đến hai đồng xu nhẹ. Đây là trường hợp thú vị đầu tiên. Câu hỏi đặt ra là: Chúng ta nên cân một đồng xu với một hay hai đồng xu với hai đồng xu?
Nếu chúng ta cân một đối một, thì chúng ta có thể có:
- Hai lần cân không cân: Phát hiện hai đồng xu; chúng ta xong rồi.
- Cân một trong hai cân: Các đồng xu cân bằng phải bình thường, vì vậy đồng xu cuối cùng cần cân một lần nữa, w = 3.
- Hai lần cân cân bằng: Trong lần cân thứ ba, cân một đồng xu từ mỗi lần cân trước với đồng xu khác. Nếu chúng cân bằng, cả bốn đều bình thường và đồng 5 là nhẹ. Chúng ta xong rồi; w = 3 lại. Nếu chúng không cân bằng, chúng tôi đã tìm thấy hai đồng xu nhẹ và chúng tôi đã hoàn thành ba lần cân.
Nếu thay vào đó, chúng ta cân hai đối hai, thì chúng ta vẫn yêu cầu ba lần cân, bởi vì chúng ta phải phân biệt khả năng các đồng xu có thể không giống nhau hoặc giống nhau ở hai bên. Việc cân sử dụng số lượng nhỏ các đồng xu được nhóm lại với nhau dường như không có bất kỳ lợi thế nào so với việc cân bằng các đồng xu đơn lẻ.
Điều này được sinh ra cho:
Sáu đồng tiền: Một đến hai đồng tiền nhẹ; w = 4.
Bảy xu: Một đến ba xu nhẹ; w = 5.
Tám đồng tiền: Một đến ba đồng tiền nhẹ; w = 6. Giải pháp này có cấu trúc đơn giản:
- Đầu tiên thực hiện bốn lần cân của một đồng xu so với đồng xu tiếp theo. Tất cả các đồng tiền được sử dụng.
- Trường hợp xấu nhất: Cả bốn lần cân đều thăng bằng (có hai đồng nhẹ cân nhau).
- Hai lần cân tiếp theo: Cân một đồng xu từ quả cân 1 so với đồng xu từ quả cân 2; tương tự, cân một đồng xu có trọng lượng 3 với đồng xu có trọng lượng 4.
- Một trong những lần cân này sẽ không cân bằng, xác định hai đồng xu nhẹ. Chúng tôi đã hoàn thành trong sáu lần cân.
Xin lỗi, dãy 0, 0, 1, 2, 3, 4, 5, 6 của chúng tôi chắc chắn không đủ thú vị để gửi đến Bách khoa toàn thư trực tuyến về dãy số nguyên!
As Jonas Tøgersen Kjellstadli chỉ ra, giải pháp dường như là w = n − 2 đối với các số nhỏ, nhưng chúng tôi chưa chứng minh được rằng điều này sẽ không thay đổi đối với các số lớn hơn. Tại một số n, sử dụng nhiều lần cân đồng xu có thể bắt đầu hoạt động tốt hơn hoặc nhiều lần cân hơn n − 2 có thể được yêu cầu. Chúng ta có thể đơn giản tổng quát hóa giải pháp cho tám đồng xu cho tất cả các lũy thừa của 2, cho n − 2 là giới hạn trên của số lần cân đối với mọi lũy thừa của 2.
Mark Pearson đã thảo luận về sự giống nhau của vấn đề này với mã sửa lỗi và đề xuất sử dụng phương pháp lý thuyết thông tin dựa trên số lượng kết quả có thể xảy ra. Sử dụng cách tiếp cận như vậy, Mike Roberts đã đăng một giới hạn dưới cho trường hợp tổng quát hơn, mà Rainer aus dem Mùa xuân rút ra một xấp xỉ cho. Rainer cũng đăng một giới hạn trên từ một bài báo đã xuất bản nhưng lưu ý rằng các giới hạn không sắc nét đối với mức thấp n và do đó không hữu ích đối với những con số nhỏ mà chúng ta đã xem xét ở trên. Do đó, đối với bảy đồng xu, các giới hạn được trích dẫn đưa ra phạm vi từ 4 đến 16, mà câu trả lời của chúng tôi, 5, nằm trong khoảng đó. J. Thanh toán cung cấp thêm tài liệu tham khảo toán học và giới hạn cho tất cả các câu đố.
Cảm ơn tất cả những người tham gia. Giải thưởng Thông tin chi tiết của tháng này cùng thuộc về Ted và Rainer aus dem Spring. Chúc mừng!
Hẹn gặp lại lần sau Insights.
