Lại về hiệp sĩ và kẻ hèn nhát

42

KVANT 2014/№3

kéo điểm trong của tam giác tới các đỉnh của nó thông qua p, q, r. Chứng minh rằng p + q + r < b + c. 9. Tìm điểm có tổng khoảng cách đến bốn điểm cho trước là nhỏ nhất (cần xét hai trường hợp: khi các điểm tạo thành một tứ giác lồi và khi một điểm nằm trong tam giác gồm ba điểm còn lại).

Tôi muốn mở rộng bộ sưu tập lời giải của mình với bài toán tuyệt vời về quan điểm của Torricelli. Nếu bạn tìm thấy một lời giải khác đẹp, vui lòng gửi cho tác giả theo địa chỉ [email protected]

Lại về hiệp sĩ và kẻ hèn nhát

Câu hỏi của chúng ta phải là một “chỉ số” về hiệp sĩ và kẻ hèn nhát: tức là hiệp sĩ phải luôn trả lời “ya”, và kẻ hèn nhát luôn phải trả lời “wa”, hoặc ngược lại. Hãy hỏi bất kỳ thổ dân nào câu hỏi “Ya - có phải không?” Tùy chọn 1: Gọi “ya” có nghĩa là “có”. Sau đó, hiệp sĩ phải trả lời “có” cho câu hỏi như vậy, tức là “ya”. Kẻ nói dối phải trả lời câu hỏi như vậy “không”, tức là “va”. Tùy chọn 2: Gọi “ya” có nghĩa là “không”. Sau đó, hiệp sĩ trả lời “không” cho câu hỏi như vậy, tức là lại “yay”! Và kẻ nói dối phải trả lời “có”, tức là “Wah” lần nữa! Vì vậy, hiệp sĩ luôn trả lời “ya” cho câu hỏi của chúng tôi và kẻ nói dối luôn trả lời “va”. Bài toán đã giải quyết.

L.BOYKO, M.BOYKO

NGƯỜI ĐỌC CHẮC CHẮN ĐÃ GẶP NHỮNG VẤN ĐỀ THÚ VỊ về những hiệp sĩ luôn nói sự thật và những kẻ dối trá luôn nói dối. Đôi khi các nhân vật khác xuất hiện trong các nhiệm vụ tương tự.

Những người xảo quyệt này là ai? Bài toán 1 (Giải đấu các thành phố XXVIII). Người ta biết rằng những kẻ dối trá luôn nói dối, những hiệp sĩ luôn nói sự thật và những kẻ xảo quyệt có thể nói dối và nói sự thật. Bạn có thể đặt những câu hỏi có thể trả lời đáp số “có” hoặc “không” (ví dụ: “Có đúng người này là người xảo quyệt không?”). Trước mặt bạn là ba người - một kẻ nói dối, một hiệp sĩ và một kẻ xảo quyệt, những người biết cái nào là cái nào. Làm thế nào bạn có thể tìm ra? bài toán này có một số lời giải. Trước khi bạn đọc một trong số chúng trong đoạn tiếp theo, hãy thử nghĩ ra ý tưởng của riêng bạn! Chìa khóa của lời giải có thể là một số câu hỏi được đặt ra cho mỗi người trong số ba người, đáp số sẽ cho biết sự khác biệt giữa một hiệp sĩ và một kẻ nói dối. Ví dụ: hãy hỏi từng người trong số ba người: “Bạn có tinh ranh không?” Hiệp sĩ sẽ trả lời “không”, kẻ nói dối sẽ trả lời “có”. Dù kẻ xảo quyệt trả lời thế nào đi nữa, trong số ba đáp số chúng tôi nhận được chỉ có một câu “không” hoặc một câu “có”. Trong trường hợp đầu tiên, chúng tôi xác định rõ ràng hiệp sĩ, bằng cách hỏi xem ai là người dễ dàng có được thông tin về hai người còn lại. Trong trường hợp thứ hai, chúng tôi xác định rõ ràng kẻ nói dối. Hơn nữa, hỏi anh ta về những người khác (có tính đến thực tế là đáp số của kẻ nói dối trái ngược với sự thật), chúng ta lại tìm hiểu thông tin về người khác.

Bài tập (Giải đấu XXVIII của các thành phố). Hãy để trong điều kiện bài toán 1 có bốn người trước mặt bạn - một kẻ dối trá, một hiệp sĩ và hai kẻ xảo quyệt (cả bốn đều biết ai là ai). Chứng minh rằng những người xảo quyệt có thể đồng ý trả lời theo cách mà bạn khi hỏi bốn người này sẽ không biết chắc chắn anh ta là ai.

Khó khăn về ngôn ngữ

Nhưng nếu bạn không biết rõ ngôn ngữ địa phương thì sao? Bài toán 2. Một số cư dân của một hòn đảo nào đó là hiệp sĩ, số còn lại là những kẻ dối trá. Người dân trên đảo hiểu ngôn ngữ của chúng tôi, nhưng chúng tôi chỉ biết ngôn ngữ của người dân đảo trong đó một từ “ya” và “va” có nghĩa là “có”, còn từ kia có nghĩa là “không” (nhưng chúng tôi không nhớ chính xác như thế nào). Chúng ta hãy gặp hai người bản xứ, một người là hiệp sĩ và người kia là kẻ nói dối. Liệu chúng ta có thể chỉ hỏi một câu hỏi (ngụ ý đáp số “có” hoặc “không”, tức là “ya” hoặc “va”), tìm ra cái nào trong số đó là cái nào không?

Một chút lịch sử Năm 1992, triết gia và nhà logic học người Mỹ George Boulos đã xuất bản bài toán, mà ông gọi là “Vấn đề logic khó nhất”. Nhìn bề ngoài, “Khó nhất bài toán” tương tự như bài toán 1 đã thảo luận ở trên, nhưng nó có thêm độ phức tạp như trong bài toán 2: các nhân vật hiểu ngôn ngữ của chúng tôi, nhưng chỉ trả lời chúng tôi bằng ngôn ngữ của họ, điều mà chúng tôi không thể hiểu được. J. Boulos gọi các nhân vật là những vị thần trong thần thoại, nhưng chúng ta sẽ cho phép mình giữ lại những nhân vật quen thuộc hơn. Ngoài ra, điều đó có vẻ tự nhiên hơn đối với chúng tôi, vì tác giả cuốn “Khó khăn nhất bài toán” J. Boulos chỉ vào Raymond Smullyan. Chúng tôi không biết liệu điều này có thực sự xảy ra hay không, nhưng R. Smullyan chắc chắn là người phổ biến bài toán loại này nổi tiếng nhất. Các tác giả của bài viết này rất quan tâm đến việc giải logic bài toán từ sách của R. Smullyan ở trường. Trong bản dịch tiếng Nga của cuốn sách này, theo quy định, chính xác những nhân vật này đã được sử dụng: hiệp sĩ và kẻ nói dối.

Tuyên bố về “Logic phức tạp nhất bài toán” Vì vậy, hãy đưa ra công thức chính xác của “Logic phức tạp nhất bài toán”. Bài toán 3. Trên đảo Java, người dân được chia thành ba loại: hiệp sĩ - những người luôn nói sự thật; kẻ nói dối là kẻ luôn nói dối; và những kẻ xảo quyệt là những người có thể nói cả sự thật và lời nói dối. Giả sử có ba người trước mặt chúng ta - ông A, ông B, ông C. Chúng ta biết rằng trong số họ có đúng một hiệp sĩ, một kẻ dối trá và một kẻ xảo quyệt, nhưng chúng ta không biết ai trong số họ là ai. Bạn cần xác định ai là hiệp sĩ, ai là kẻ nói dối và ai là kẻ xảo quyệt bằng cách hỏi không quá ba câu hỏi. Các câu hỏi phải sao cho có thể trả lời “có” hoặc “không”. Mỗi câu hỏi chỉ được hỏi cho một người. Một điều phức tạp nữa là người dân trên đảo hiểu ngôn ngữ của chúng tôi nhưng chỉ trả lời chúng tôi bằng ngôn ngữ của họ. Chúng ta biết rằng trong ngôn ngữ này có hai từ “ya” và “wa”, có nghĩa là “có” và “không”, nhưng chúng ta không biết từ nào có nghĩa là “có” và từ nào có nghĩa là “không”. Chúng ta hãy đưa ra một số giải thích cho cách diễn đạt mà J. Boulos chỉ ra trong bài viết của mình. i Bạn có thể hỏi nhiều câu hỏi cho một người (trong trường hợp đó những người khác không được hỏi bất kỳ câu hỏi nào).

43

TOÁN HỌC

i Câu hỏi tiếp theo là gì và hỏi ai có thể phụ thuộc vào đáp số của câu hỏi trước. Bạn không thể hỏi những câu hỏi nghịch lý mà có thể trả lời bằng cả “có” và “không” hoặc không thể trả lời được chút nào. Ví dụ: “Bây giờ bạn có định trả lời ‘ya’ không?” i Kẻ ranh mãnh trả lời các câu hỏi một cách hoàn toàn tùy tiện. Chúng ta có thể giả định rằng mỗi lần anh ta gieo một đồng xu trong tâm trí và nếu nó ngửa thì anh ta trả lời sự thật, còn nếu nó ngửa thì anh ta nói dối. Nói thêm rằng, tất nhiên, ông A, B và C biết nhau và biết ai là kẻ dối trá, ai là hiệp sĩ, ai là kẻ gian xảo. Trước khi trình bày lời giải, chúng ta hãy giới thiệu hai cấu trúc tinh thần.

Ông Ya, ông Wa và ông Hee Ở trên, chúng tôi gọi hiệp sĩ là người luôn nói sự thật. Nói cách khác, chúng ta có thể nói điều này: hiệp sĩ là người trả lời “có” nếu tuyên bố trong câu hỏi là đúng. Đồng thời, kẻ nói dối là người trả lời “không” cho câu nói như vậy. Chúng ta hãy nhớ rằng người dân trên đảo sử dụng ngôn ngữ riêng của họ. Do đó, đối với một câu hỏi khẳng định đúng, cả hiệp sĩ và hiệp sĩ đều trả lời luôn là “ya” hoặc luôn là “va”. Người trả lời “Ya” sẽ được đặt tên đệm – Mr. Ya. Và người luôn trả lời “va” sẽ được gọi là anh Va. Cuối cùng, chúng ta sẽ gọi người đàn ông xảo quyệt là anh He. Lưu ý rằng chúng ta không thể biết ông Ya là hiệp sĩ hay kẻ nói dối, nhưng chính những người dân đảo A, B và C phải biết cái nào là cái nào. Vì vậy chúng ta có thể sử dụng tên mới trong câu hỏi. Ví dụ: chúng ta có thể hỏi anh A, “Anh có phải là anh Ya không?” hoặc hỏi anh ta: “Anh B là anh Va phải không?”

Bộ bài Bây giờ lấy ba tờ giấy giống hệt nhau và viết “Mr. Ya” trên tờ đầu tiên, “Mr. Wa” trên tờ thứ hai và “Mr. Hee” trên tờ thứ ba. Chúng ta sẽ nhận được ba lá bài - lá Ya, lá Wa và lá Hi.

Có sự tương ứng tự nhiên giữa người và thẻ. Vì vậy, nếu khái niệm “thẻ của ông A” xuất hiện trong một câu hỏi thì người dân trên đảo nên hiểu như sau: họ cần tra xem ông A là ai - ông Ya, Wa hay Hi - và tìm một tấm thẻ có ghi tên tương ứng trên đó. Điều tương tự cũng nên được thực hiện nếu câu hỏi có chứa khái niệm “thẻ của bạn”. Bây giờ chúng ta hãy đặt ba lá bài này vào một bộ bài: lá Ya ở trên, sau đó là lá Wa và lá dưới cùng – lá Hi. Nếu không có giấy và không làm được bộ bài như vậy thì chúng ta phải yêu cầu người dân trên đảo làm một thí nghiệm tư duy: hãy tưởng tượng ba lá bài này theo thứ tự như vậy. Tại sao thứ tự thẻ này được chọn? Chúng tôi sẽ giải thích điều này một lát sau. Trong các câu hỏi sau này, chúng ta sẽ gặp khái niệm “một quân bài nằm trên một quân bài khác”. Trong trường hợp này chúng tôi

VÒNG TRÒN

Chúng ta hiểu như sau: lá bài này cao hơn lá bài kia trong bộ bài, và hai lá bài này nằm liền kề nhau trong bộ bài. Như vậy, trong bộ bài của chúng ta, quân Ya nằm trên quân Ba, quân Wa nằm trên quân Hi. Nhưng thẻ Ya KHÔNG nằm trên thẻ Hi. Bây giờ chúng ta có thể chuyển trực tiếp đến các câu hỏi để xác định ai là người dân trên đảo.

Lời giải bài toán 3

Câu hỏi đầu tiên

Hãy hỏi anh A như sau: “Bộ bài của anh có nằm trong bộ bài của anh B không?” Hãy chứng minh rằng trong trường hợp đáp số “ya” của câu hỏi này, anh B không phải là người xảo quyệt (anh ấy là hiệp sĩ hoặc kẻ nói dối), và trong trường hợp đáp số “va” của câu hỏi này, anh B không phải là Hi. Lưu ý rằng nếu A là ông Xi thì cả B và C đều không thể là Xi, đó là điều chúng ta cần. Giả sử rằng anh A không phải là anh ấy và xem xét các lựa chọn đáp số của anh ấy cho câu hỏi. Hãy để A trả lời “ya”. Phương án 1: Ông A là ông Ya. Khi đó khẳng định trong câu hỏi là đúng và thẻ của anh A là thẻ của Y. Vì trong bộ bài lá Ya nằm trên lá Wa nên ông B là ông Va. Phương án 2: Ông A là ông Ba. Vì ông Wa trả lời “ừ” nên khẳng định “Thẻ của ông A nằm trên thẻ của ông B” là sai. Điều này có nghĩa là quân bài Wa không nằm trên quân bài của ông B. Theo định nghĩa của bộ bài, lá Wa nằm trên lá Chi. Vậy ông B không phải là Ông. Hãy để A trả lời “va”. Phương án 1: Ông A là ông Ya. Tuyên bố trong câu hỏi là sai. Lá bài Ya nằm trong bộ bài của lá bài Wa và không nằm trên lá bài Hi. Vậy ông B là Ông và ông C là ông Wa. Phương án 2: Ông A là ông Ba. Tuyên bố này là đúng. Lá bài Wa nằm trong bộ bài trên lá Chi. Vậy ông B là ông, ông C là ông Ya.

Câu hỏi thứ hai

Với câu hỏi đầu tiên, chúng tôi xác định được anh B và anh C chắc chắn không phải là người xảo quyệt. Câu hỏi thứ hai cần được hỏi cụ thể với người dân đảo này, một người không phải là người xảo quyệt. Trong cả hai trường hợp, câu hỏi sẽ giống nhau và rất giống với câu hỏi trước: “Có phải quân bài của bạn nằm trong bộ bài của ông A không?” Như chúng ta đã thấy ở trên, đáp số câu hỏi này cho chúng ta thấy trong số hai người dân trên đảo (những người mà câu hỏi hiện tại không đề cập đến) một người chắc chắn không phải là ông He. Để cụ thể hơn, hãy xem xét trường hợp khi câu hỏi được đặt ra bởi B. Khi đó A hoặc B không phải là Xi. Gọi B. Thì Hee là ông A. Tương tự, trong mọi trường hợp có thể ta đều nhận ra ông Hee là ai.

Câu hỏi thứ ba

Vì vậy, với hai câu hỏi trước, chúng tôi đã tìm thấy ông He trong số những người dân trên đảo. Như trong lời giải bài toán 2, hãy hỏi bất kỳ ai trong số hai cư dân còn lại trên đảo câu hỏi “chỉ số” của các hiệp sĩ và những kẻ nói dối “Ya là Yes?” và từ đó tìm ra ai là ai. Thuật toán được trình bày và bài toán đã được giải quyết! lời giải đã cho gần giống với bản gốc lời giải của J. Boulos về mặt ý thức hệ. Tuy nhiên, hai cấu trúc tinh thần - tên mới của người và một bộ bài (mối quan hệ giữa các tên mới) - giúp tránh được các câu lệnh có điều kiện, và