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

Ответ. Б – мафиози, Г и Д – мирные жители.

Занятие 10

10.6. Если белых колпаков по-прежнему два, а черных более трех (например, 4 или 5), то все рассуждения останутся в силе. А вот если мудрецам принести три белых и три черных колпака и надеть на каждого черный колпак, третий мудрец тоже не сможет определить цвет своего колпака, но доказать это непросто. Заметим, что в таком случае после того, как все три мудреца по очереди скажут «не знаю», первый уже сможет определить цвет своего колпака.

10.7. Сначала сформулируем общую задачу.

По кругу сидят n мудрецов, они могут видеть и слушать друг друга. Им принесли n — 1 белый и n черных колпаков. Затем завязали глаза, надели всем черные колпаки, а белые спрятали. После этого мудрецам развязали глаза и стали поочередно спрашивать: «Знаешь ли ты цвет своего колпака?» Почти все ответили: «Не знаю», а последний сказал: «Знаю. Черный». Как он рассуждал?

Приведем рассуждения четвертого мудреца для n = 4. «Если на мне белый колпак, то остались два белых и четыре черных колпака. Но в таком случае третий мудрец смог бы определить, что у него черный колпак (для этого ему пришлось бы всего лишь решить предыдущую задачу). Раз он сказал, что не знает, на мне черный колпак».

Рассуждения последующих мудрецов аналогичны. Строгое решение задачи о мудрецах в общем виде можно изложить с помощью метода математической индукции.

10.8. Подсказка. Решите сначала задачу для одного мудреца, затем постепенно увеличивайте их количество.

Решение. 1) Если бы грязный мудрец был один, он вышел бы на первой станции.

Если грязных мудрецов двое, то на первой станции каждый понадеется, что грязный другой, поэтому никто не выйдет. После этого первый мудрец подумает: «Если бы я был чист, второй мудрец догадался бы, что он грязный, и вышел бы на первой станции. Но он не вышел, следовательно, я испачкался». Так же подумает и второй мудрец, и оба выйдут на второй станции.

Если грязных мудрецов трое, то на первых двух станциях никто не выйдет. А перед третьей третий мудрец подумает: «Если мое лицо чистое, то двое оставшихся мудрецов должны вести себя так, словно меня нет. Но в таком случае они вышли бы на второй станции. Раз они не вышли, мое лицо грязное». Так же подумают и два первых мудреца, и все трое выйдут на третьей станции.

Рассуждая аналогично, получаем, что все семь мудрецов выйдут на седьмой станции.

2) Снова начнем с простых случаев. Если мудрец один, то от проводника он узнал, что кто-то испачкался. Если мудрецов двое, то каждый и без проводника знал, что кто-то испачкался. Но из слов проводника он понял, что и другой знает, что кто-то испачкался.

Пусть мудрецов трое. Третий видел грязные лица первого и второго и понимал, что первый и второй знают, что кто-то испачкался. Но вот знает ли второй, что первый знает, что кто-то испачкался? Знает, но это стало известно третьему лишь после слов проводника. Это же можно сказать и о других мудрецах. Итак, все мудрецы узнали, что все знают, что все знают, что кто-то испачкался.

Рассуждая аналогично, добираемся до семи мудрецов. Из слов проводника все узнали, что все знают, что все знают, что все знают, что все знают, что все знают, что все знают, что кто-то испачкался. Заметим, что глагол «знать» повторяется столько же раз, сколько было мудрецов и станций.

10.9. «Среди вас есть испачкавшиеся» означает, что на ком-то надет черный колпак. Никто не сообщал это мудрецам словами. Но зато они видели, что белых колпаков на один меньше, чем мудрецов.

Комментарий. А если бы их было на два меньше? Тогда как минимум на двух мудрецах были бы черные колпаки. Это бы соответствовало словам проводника «Среди вас как минимум двое испачкались». В таком случае мудрецы бы вышли на одну станцию раньше (а в задаче про колпаки цвет своего колпака назвал бы предпоследний мудрец).

Заметим, что для полного соответствия задач следовало не спрашивать мудрецов поочередно, а всех мудрецов одновременно просить написать, знают ли они цвет своего колпака, а затем показывать записки друг другу.

10.10. Смех.

10.11. Приведем возможный пример.

1. Вор Карл украл кораллы.

2. Его друг Фридрих знает, что Карл украл кораллы (но не доносит).

3. Следователь Шерлок знает, что Фридрих знает, что Карл украл кораллы (и хочет арестовать Фридриха).

4. Клара знает, что Шерлок знает, что Фридрих знает, что Карл украл кораллы (и предупреждает Фридриха, что ему надо скрыться).

5. Шерлок знает, что Клара знает, что Шерлок знает, что Фридрих знает, что Карл украл кораллы (и хочет допросить Клару).

6. Клара знает, что Шерлок знает, что Клара знает, что Шерлок знает, что Фридрих знает, что Карл украл кораллы (и благополучно скрывается вместе с Фридрихом).

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

Д1. Если Саша мальчик, а Женя девочка, то оба ребенка говорят правду. Противоречие. Если Саша девочка, а Женя мальчик, то оба ребенка врут, что не исключается условием «хотя бы один из них врет».

Ответ. Саша – девочка, а Женя – мальчик.

Д2. Рассмотрим честного конгрессмена в паре со всеми остальными по очереди. По условию 2 второй в паре всегда продажен.

Ответ. Один.

ДЗ. 1) Легко видеть, что Ваня говорит правду (если предположить, что он лжет и высказывание «Я не всегда говорю правду» не является правдой, то правдой будет: «Я всегда говорю правду», т. е. получится противоречие).

2) Так как смысл высказывания Антона такой же, то Антон тоже говорит правду.

3) По условию, один из мальчиков солгал, значит, это – Саша.

4) Саша сказал: «Антон не всегда говорит правду» – и при этом солгал, значит, Антон всегда говорит правду.

Ответ: Антон.

Д4. В этом утверждении говорится об истинности его самого. Поэтому его нельзя считать не истинным, ни ложным, то есть оно вообще не является высказыванием.

Комментарий. Рассмотрим такое решение. «Если это высказывание истинно, т. е. правил без исключения нет, то и из этого правила есть исключения, и правила без исключения все-таки есть. Пришли к противоречию. Значит, высказывание ложно, и существует хотя бы одно правило без исключения (хотя и не это)». Ошибка выходит на поверхность, если представить, что это правило единственное. И тогда правилу без исключения взяться неоткуда. Если же заранее договориться, что существуют хотя бы два правила, то эту фразу можно считать ложным высказыванием. Аналогично, если считать, что на Крите есть хотя бы два жителя, и только один из них сказал «Все критяне лжецы», парадокс Эпименида перестает быть парадоксом.

Д5. 1) Не каждый охотник желает знать, где сидит фазан. 2) Существует хотя бы один охотник, не желающий знать, где сидит фазан. 3) Некоторые охотники не желают знать, где сидит фазан.

Д6. Все лжецами быть не могли (в таком случае сказанное каждым оказалось бы правдой), был хотя бы один рыцарь. Он сказал правду, поэтому все остальные были лжецами.

Ответ. Один.

Д7. Первое можно опровергнуть контрпримером (начертив прямоугольник с неравными сторонами), третье и четвертое доказать примером (начертив любой квадрат), а доказать второе помогут определения прямоугольника и квадрата.

Ответ. Первое утверждение ложно, а остальные истинны.

Д8. 1) Некоторые друзья моего друга не являются моими друзьями. 2) Некоторые ананасы приятны на вкус. 3) Ни один волк не является оборотнем.

Д9. Чтобы разобраться в трех замысловатых условиях, удобно для начала перечислить все возможные виды зоопарков с точки зрения наличия жирафов, носорогов и гиппопотамов. Их всего восемь:

1) ЖНГ; 2) ЖНГ; 3) ЖНГ; 4) ЖНГ;

5) ЖНГ; 6) ЖНГ; 7) ЖНГ; 8) ЖНГ.

Здесь запись ЖНГ, например, означает, что в зоопарке есть жирафы, нет носорогов и есть гиппопотамы. В силу первого условия вычеркиваем зоопарки вида 1, в силу второго – вида 7, в силу третьего – вида 2. Теперь видно, что ничто не противоречит существованию зоопарков вида 6.

Эти рассуждения могут быть изображены с помощью кругов Эйлера. Области на рис. 30 пронумерованы в соответствии с приведенным списком. Зоопарки, запрещенные условием, закрашены серым. Зоопарки, соответствующие остальным областям, могут существовать, в том числе и соответствующие шестой области.

Ответ. Да.

Рис. 30

Д10. Чтобы выполнить пожелание Ани, необходимы и яблоки, и сливы. Чтобы порадовать Галю, нужны еще и персики. Остается лишь проверить, что Боря и Витя при этом тоже будут довольны.

Ответ. Надо купить яблоки, сливы и персики.

Д11. 1) Луна сделана не из сыра или Солнце не из масла.

2) Я не видел медведя или он видел меня.