Логика для всех. От пиратов до мудрецов

Ответ. Пятый и третий скажут «Не знаю», а остальные назовут свой цвет.

Два мудреца и последовательные числа

Задача 10.14. 1) Двум мудрецам написали на лбу по натуральному числу и сообщили, что эти числа последовательные. Когда мудрецы посмотрели друг на друга, между ними состоялся такой диалог:

А: «Я не знаю моего числа».

Б: «А я знаю мое число».

Какие числа были написаны?

Решение. Если бы А увидел число 1, то он бы понял, что у него на лбу число 2. То есть А фактически сообщил Б, что у него не 1. Если Б увидел число 2, то он сделал вывод, что у него самого – 3. Если Б увидел 1, то он независимо от слов А понял, что у него самого 2. А если бы Б увидел другое число, он не смог бы определить свое число.

Ответ. Либо у А написано число 2, а у Б – число 3, либо у А – число 1, а у Б – число 2.

Сценарий. После разбора этой задачи можно поиграть с числами чуть побольше (3 и 4, 4 и 5, 5 и 6). Рисовать каждый раз на лбу необязательно, можно использовать наклейки на лоб, а чтобы зрителям было труднее, можно писать числа на бумажках. Двум школьникам дают написанные на бумажках последовательные числа (причем делать это могут зрители), а они по очереди говорят, знают ли они, что написано на бумажке у второго «мудреца». Когда один из них скажет «Знаю», зрители должны догадаться, какие у них числа, и проверить, не ошибся ли кто-то из «мудрецов». Интересно сравнить, как изменится диалог, если дать мудрецам те же числа, но в обратном порядке. Экспериментируя, школьники могут заметить, что первым догадывается о числе партнера тот из мудрецов, кто видит меньшее число. После этого можно предложить исследовать ситуацию в общем виде.

2) Каждому из двух мудрецов дали бумажку с написанным на ней натуральным числом и сообщили, что эти числа последовательные. Когда мудрецы посмотрели на числа, между ними состоялся такой диалог:

А: «Я не знаю твое число».

Б: «И я не знаю твое число».

А: «И я не знаю твое число».

…

а) Докажите, что рано или поздно кто-то из мудрецов сможет сказать: «Теперь я знаю твое число».

б) От чего (от написанных чисел или от того, кто начал диалог) зависит, кто из мудрецов первым узнает число другого?

в) Докажите, что второй мудрец сможет сказать в ответ: «И я теперь тоже знаю твое число».

Решение, а) Произнося по очереди «Я не знаю твое число», мудрецы сообщают друг другу следующую информацию:

А: «У меня не 1»;

Б: «У меня не 1 и не 2»;

А: «У меня не 1, не 2 и не 3» и так далее, прибавляя по одному числу с каждым новым высказыванием.

Ясно, что это не может продолжаться бесконечно.

б) Пусть одному из мудрецов (неважно, А или Б) написали меньшее число n, а второму – большее число n + 1. До (n — 1) – го высказывания никто из них не знает, какое число у партнера. Если (n — 1) – е высказывание делает второй, то первый поймет, какое у него число, и скажет об этом. Если (n — 1) – е высказывание делает первый, то второй не сможет сразу определить, какое число у первого, n или n + 2, и сделает n-е высказывание: «И я не знаю твое число». А первый теперь все поймет.

в) Как выяснилось в предыдущем пункте, сказав «Теперь я знаю твое число», первый мудрец фактически сообщает: «Мое число меньше твоего». Второму мудрецу остается лишь отнять 1 от своего числа.

3) Каждому из двух мудрецов дали бумажку с написанным на ней натуральным числом и сообщили, что эти числа последовательные. Когда мудрецы посмотрели на числа, между ними состоялся такой диалог:

А: «Я не знаю твое число».

Б: «И я не знаю твое число».

А: «И я не знаю твое число».

Б: «И я не знаю твое число».

После того как каждый сообщил о своем незнании 10 раз, мудрец А сказал: «Теперь я знаю твое число». Какие числа были написаны на бумажках?

Ответ. Либо у А число 20, а у Б число 21, либо у А число 21, а у Б число 22.

Решение. После первой реплики А мудрец Б понимает, что у А не число 1. Если бы у Б было число 2, он бы понял, что у А число 3. По его первой реплике ясно, что это не так (а также что у Б не 1), и мудрец А делает вывод, что у Б не 1 и не 2. Рассуждая аналогично, делаем два вывода. Во-первых, после десятой реплики А мудрец Б понимает, что у А не числа от 1 до 19 включительно. Во-вторых, после десятой реплики Б мудрец А понимает, что у Б не числа от 1 до 20 включительно. Понять после этого, какое у Б число, мудрец А мог в двух случаях: если у него самого число 20, то у Б число 21, а если у А число 21, то у Б – 22.

Дополнительные задачи

Трудные задачи решаем немедленно, невозможные – чуть погодя.

«Все» и «некоторые»

Задача Д1. На крыльце дома сидят рядом мальчик и девочка. Саша говорит: «Я мальчик». Женя говорит: «Я девочка». Хотя бы один из них врет. Кто мальчик, а кто девочка?

Задача Д2. В некоем конгрессе заседают 100 политических деятелей. Каждый из них либо продажен, либо честен. Известно, что:

1) по крайней мере один из конгрессменов честен;