Về những người trung thực, những kẻ nói dối và những kẻ lừa dối

8

Về con người
Phải,
những kẻ nói dối
và những kẻ lừa dối

Trong số bài toán toán học, bài toán logic được trí thông minh đặc biệt quan tâm. bài toán như vậy, theo quy luật, không yêu cầu kiến ​​​​thức toán học đặc biệt và các điều kiện của chúng có thể được giải thích ngay cả với những người có thang đo ở xa toán học.

Bây giờ chúng ta sẽ phân tích bốn logic bài toán. Trong những nhiệm vụ này, chúng ta sẽ có những người đúng, trong mọi trường hợp chỉ nói sự thật và những kẻ nói dối, luôn chỉ nói sự thật. Tuy nhiên, khó nhất và thú vị nhất, như chúng ta sẽ thấy, sẽ là những bài toán trong đó cũng có những kẻ lừa dối, tức là những người nói bất cứ điều gì chỉ để khiến người hỏi bối rối.

Bài toán 1*). Ở ngã ba của hai con đường, một trong số đó dẫn đến thành phố A, có hai người trung thực sống và con đường kia dẫn đến thành phố B, hai kẻ nói dối sống, một nhà toán học đã gặp một cư dân của một trong những thành phố này. Liệu một nhà toán học, với một câu hỏi, có thể tìm ra từ một người dân mà anh ta gặp con đường nào dẫn đến thành phố A?

Đáp số trong bài toán 1 là tích cực ngay cả trong một điều kiện bổ sung mà chúng tôi sẽ luôn giữ trong trường hợp có câu hỏi để đáp số phục vụ nó

*) Bài toán 1 và 2 được nhà toán học người Hungary P. Major truyền đạt cho tác giả.

những từ “có” và “không” vẫn tồn tại. Câu hỏi quyết định bài toán 1 là: “Con đường này (chỉ vào một trong những con đường) có dẫn đến quê hương của bạn không?” Dễ dàng kiểm tra rằng đáp số “có” có nghĩa là con đường này dẫn đến A, đáp số “không” - đến B. Trên thực tế, nếu người trả lời là cư dân của thành phố A, thì anh ta luôn nói sự thật và do đó đáp số “có” của anh ta có nghĩa là con đường được chỉ định không dẫn đến B, tức là đến A, và đáp số “không” có nghĩa là con đường này dẫn đến quê hương của anh ta, tức là đến B. Do đó, trong trường hợp chung, đáp số “có” có nghĩa là con đường đã cho dẫn đến A, và đáp số “không” có nghĩa là nó dẫn đến B, như đã nêu.

Lưu ý rằng tại đáp số, chúng tôi không xác định rằng chúng tôi đang nói chuyện với cư dân của thành phố A hoặc với cư dân của thành phố B, nhưng điều này không bắt buộc. Tác giả biết về lời giải bài toán 1 khác, ​​nhưng tất cả đều dựa trên cùng một ý tưởng: câu hỏi liệu một con đường nhất định có dẫn đến thành phố A hay không phải được hỏi dưới dạng sao cho người nói dối nhận được “phủ định kép” đáp số. Vì số âm kép tương đương với số dương đáp số, nên kẻ nói dối trong trường hợp này sẽ đưa ra đáp số giống như người nói thật. Đây là những gì xảy ra trong lời giải mà chúng tôi đã trích dẫn.

bài toán thứ hai mà chúng ta sẽ phân tích là điều kiện của điều kiện đầu tiên. Đây là những điều kiện liên quan đến sự xuất hiện của kẻ lừa dối trong số những người được hỏi.

Bài toán 2. Giả sử trong điều kiện bài toán 1, nhà toán học gặp nhau ở ngã ba đường không phải một mà là ba người, một người là cư dân thành phố A, người thứ hai là cư dân thành phố B, và người thứ ba là kẻ lừa dối. Hơn nữa, nhà toán học biết rằng trong số ba người này, một người là cư dân thành phố A, một người là cư dân thành phố B, và người thứ ba là kẻ lừa dối, nhưng không biết cụ thể ai trong số họ là ai. Một nhà toán học có thể tìm ra đường đến A trong hai câu hỏi không?

9

Hãy để chúng tôi làm rõ rằng mỗi câu hỏi trong số hai câu hỏi có thể được hỏi cho bất kỳ ai trong số ba người mà nhà toán học gặp ở ngã ba, và câu hỏi chỉ được trả lời bởi người được hỏi câu hỏi này. Ngoài ra, tất cả những người anh gặp đều biết “ai là ai” trong số họ và con đường nào dẫn đến A và con đường nào dẫn đến B.

Lời giải bài toán 1 được gọi đến suy nghĩ: liệu câu hỏi đầu tiên có thể chọn ra trong số ba người một người không phải là kẻ lừa dối không? Sau đó, bài toán 2 sẽ giảm xuống còn bài toán 1 và bằng cách hỏi người được đánh dấu câu hỏi tương tự như trong bài toán 1, chúng tôi đã tìm ra đường đến A. Hóa ra là có thể hỏi câu hỏi đầu tiên như vậy, mặc dù đối với tác giả, có vẻ như nó không dễ đoán.

Chúng ta hãy đánh số lại ngẫu nhiên cả ba người cho thuận tiện. Câu hỏi được đặt ra đầu tiên. Đây là: “Giả sử bây giờ ba bạn đi đến A hoặc B theo nguyên tắc sau: cư dân thành phố A sẽ đến thành phố A, cư dân thành phố B sẽ đến thành phố B, và kẻ lừa dối - trừ khi chính bạn là kẻ lừa dối - sẽ đi cùng bạn, nếu bạn là kẻ lừa dối thì bạn sẽ đi bất cứ đâu. Với những điều kiện này, người này (chỉ vào người thứ hai) có đi đến Nhưng không?”

Chúng tôi khẳng định rằng với đáp số “có” thì người thứ ba không phải là kẻ lừa dối và với đáp số “không” thì người thứ hai không phải là kẻ lừa dối. Thật vậy, nếu chúng tôi đặt một câu hỏi cho một kẻ lừa dối, thì người thứ hai và thứ ba trong số những người được phỏng vấn không phải là kẻ lừa dối và do đó, người thứ ba cũng không phải vậy. Ngược lại, đáp số “không” của anh ta chỉ ra rằng người thứ hai là kẻ nói dối (dù sao thì chỉ có kẻ nói dối mới không đi cùng anh ta). Nếu chúng ta đặt câu hỏi cho một kẻ nói dối, thì “có” của anh ta có nghĩa là vì kẻ lừa dối đi đến B, và người nói sự thật đi đến A, nên người thứ hai là kẻ lừa dối, và người thứ ba là người nói sự thật. “Không” nghĩa là ngược lại, người thứ hai là người nói thật, người thứ ba là kẻ lừa dối.

Phân tích tất cả các khả năng, không khó để nhận thấy rằng với đáp số “có” người thứ ba, và với đáp số “không” người thứ hai phụ thuộc, họ không phải là kẻ lừa dối. Do đó, trong cả hai trường hợp, chúng ta có thể chỉ ra một người không phải là kẻ lừa dối và do đó vấn đề 2 đã được giải quyết.

Lưu ý rằng, giống như với lời giải bài toán 1, mục đích chính là buộc người nói dối phải phủ định kép, tức là để đảm bảo rằng đáp số của anh ta có cùng ý nghĩa với ý nghĩa của người nói sự thật và để họ có thể phân biệt giữa người lừa dối và người không lừa dối.

Nhiệm vụ 3. N nhà khoa học đi đến khái niệm hóa học; một số trong số họ là Khimki, số còn lại là nhà giả kim, và người ta biết rằng còn có nhiều Khimki hơn. Nhà hóa học trả lời trung thực mọi câu hỏi, nhưng nhà giả kim luôn nói dối. Một nhà toán học đã nảy ra khái niệm này và bắt đầu xác định về tất cả các nhà khoa học, ai trong số họ là nhà hóa học và ai là nhà giả kim. Để làm điều này, anh ta được phép hỏi bất kỳ nhà khoa học nào về bất kỳ nhà khoa học nào khác mà anh ta là ai. Nêu cách mà một nhà toán học có thể tìm ra “ai là ai” trong (N—1) câu hỏi.

Lời giải bài toán 3 tương đối dễ. Cụ thể, hãy hỏi bất kỳ nhà khoa học nào (hãy gọi anh ta trước để định nghĩa) về từng nhà khoa học khác. Kết quả là, các nhà khoa học (N-1) này sẽ được chia thành hai nhóm: nhóm gồm những người, theo nhà khoa học thứ nhất, là nhà hóa học, và nhóm gồm những người, theo nhà khoa học thứ nhất, là nhà giả kim. Hãy phân loại nhà khoa học đầu tiên là nhóm đầu tiên. Hãy chọn nhiều hơn từ các nhóm này. Vậy thì các nhà khoa học của nhóm này là nhà hóa học, các nhà khoa học của nhóm kia là nhà giả kim (chứng minh đi!). Như vậy vấn đề đã được giải quyết.

Bây giờ chúng ta đến trọng tâm bài toán của bài viết - bài toán M585 («Kvant», 1979, Số 9). Các điều kiện của nó trùng với các điều kiện của bài toán 3, ngoại trừ việc các nhà giả kim không còn là những kẻ nói dối nữa mà là những kẻ lừa dối. Trong bài toán M585

10

Người ta phải tìm ra “ai là ai” tại hội nghị bằng các câu hỏi a) 4N, 6) 2N-2, c) [3N/2].

bài toán này phức tạp hơn nhiều so với bài toán 3, và một lần nữa điều này là do thực tế là đáp số của một kẻ nói dối, mặc dù chúng không chính xác, nhưng có thể nói, chúng “liên tục không chính xác”, cho phép chúng ta trích xuất từ ​​chúng những thông tin gần giống như thông tin chính xác của đáp số của một người trung thực. Đáp số của kẻ lừa dối là tùy tiện, và việc lấy bất kỳ thông tin nào từ họ là bài toán của thành phố khó khăn hơn.

lời giải được đưa ra dưới đây giúp bạn có thể tìm ra ai là nhà hóa học và ai là nhà giả kim, thậm chí với số lượng câu hỏi ít hơn [3N/2], cụ thể là trong các câu hỏi $q=3k$ nếu $N=2k+1$ là số lẻ và trong các câu hỏi $q=3(k-1)$ nếu $N=2k$ là số chẵn.

Trước tiên chúng ta sẽ xem xét số lẻ $N$. Chúng ta sẽ xác định phương pháp cần thiết bằng quy nạp trên $k$. Nếu $N=1$ nhà khoa học ($k=0$) có mặt tại hội nghị, thì anh ta rất/không phải là nhà hóa học, vì lẽ ra sẽ có nhiều nhà hóa học hơn; Không cần phải hỏi bất kỳ câu hỏi nào trong trường hợp này: $q=0=3\cdot0$.

Bây giờ giả sử rằng với tất cả các số lẻ nhỏ hơn $N=2k+1$, chúng ta đã có cách giải bài toán với số lượng câu hỏi yêu cầu. Hãy để chúng tôi chỉ ra phương pháp này cho số $N=2k+1$. Để thuận tiện cho tất cả những người tham gia hội nghị, hãy đánh số lại họ một cách ngẫu nhiên và bắt đầu hỏi nhà khoa học thứ hai, thứ ba, v.v. ai là nhà khoa học đầu tiên. Chúng tôi sẽ dừng yêu cầu này ngay khi một trong hai sự kiện xảy ra:

Sobtiye A. Trong số các nhà khoa học được khảo sát, phần lớn đều ủng hộ việc nhà khoa học đầu tiên là một nhà giả kim.

Sự kiện V. Số lượng các nhà khoa học, người ta cho rằng nhà khoa học đầu tiên là một nhà hóa học, bằng $k$.

Rõ ràng là nếu sự kiện $A$ xảy ra và đến thời điểm này, $t$ các nhà khoa học tuyên bố rằng nhà khoa học đầu tiên là một nhà hóa học và $f$ rằng ông ấy là một nhà giả kim, thì $f=t+1$. (Thật vậy, $f>t$, và nếu chúng ta giả sử rằng $f\geq t+2$, thì sự kiện $A$ phải xảy ra ít nhất một câu hỏi trước đó.) Cũng rõ ràng là trong trường hợp này, cuộc khảo sát đã đặt ra $q_1=f+t=2f-1$ câu hỏi. (Trường hợp đặc biệt của sự kiện $A$ là tình huống nhà khoa học thứ hai nói rằng người thứ nhất là nhà giả kim - ở đây $t=0$, $f=1$.)

Nếu sự kiện $B$ xảy ra và đồng thời $f$ các nhà khoa học tuyên bố rằng nhà khoa học đầu tiên là một nhà giả kim, thì tổng số câu hỏi được đặt ra là $q_1=k+f$.

Không khó để nhận thấy cuộc thăm dò đã xoay chiều trước khi tất cả các nhà khoa học tham dự hội nghị đều được bỏ phiếu. Trên thực tế, hãy giả sử điều ngược lại. Điều này có nghĩa là trước khi nhà khoa học cuối cùng được phỏng vấn, sẽ không có sự kiện $A$, $B$ nào xảy ra. Hãy để tại thời điểm này trong số các nhà khoa học được khảo sát $t$ một người lên tiếng rằng nhà khoa học đầu tiên là một nhà hóa học và $f$ rằng anh ta là một nhà giả kim. Vì sự kiện $A$, $f\leq t$ đã không xảy ra. Vì sự kiện $B$, $t\leq k-1$ đã không xảy ra. Do đó, tổng số người trả lời là $f+t\leq 2(k-1)$. Thêm các nhà khoa học đầu tiên và cuối cùng vào họ, chúng ta nhận được rằng tổng số người tham gia hội nghị không vượt quá $2k$, trong khi có $2k+1$. Kết quả mâu thuẫn chứng tỏ rằng một trong các sự kiện - $A$ hoặc $B$ - sẽ xảy ra trước khi nhà khoa học cuối cùng được thăm dò ý kiến.

Cho sự kiện $A$ xảy ra. Khi đó chúng tôi khẳng định rằng trong nhóm các nhà khoa học, trạng thái của nhà khoa học đầu tiên và tất cả các nhà khoa học được khảo sát, số nhà giả kim không ít hơn số nhà hóa học.

Thật vậy, nếu nhà khoa học đầu tiên là một nhà hóa học, thì $f$ các nhà khoa học tuyên bố rằng anh ta là nhà giả kim chính là những nhà giả kim. Vì tổng số nhà khoa học trong nhóm đang được xem xét là $1+t+f=2f$ nên số nhà giả kim trong nhóm trong trường hợp này không ít hơn số nhà hóa học. Nếu nhà khoa học đầu tiên là một nhà giả kim, thì $t$ các nhà khoa học tuyên bố rằng ông ta là nhà hóa học cũng là nhà giả kim. Pozny và trong trường hợp này là số lượng nhà giả kim