Занятие 1

1.5. 1) Это не только не высказывание, но и вообще не утверждение. Данное предложение побудительное, а высказывание всегда является повествовательным предложением. Например, «Все умные люди перед тем, как что-либо отрезать, проводят семикратные измерения». Истинность такого высказывания весьма сомнительна.

2) Грамматическая структура этого предложения слишком сложна. При желании можно превратить поэтическую истину в аналогичное по смыслу ложное высказывание «Для того чтобы жить в доме, достаточно его нарисовать». Только зачем?

3) Чтобы превратить это утверждение в высказывание, надо точно указать время и место.

1.7. 1) Да. 2) Нет. Митя и Андрей могут иметь одинаковый рост.

1.8. 1) Достаточно ли заменить дальнюю дорогу на ближнюю? Нет, поскольку завтра королю вообще может быть не суждено никакой дороги. Можно поставить перед глаголом частицу «не»: «Завтра королю не выпадает дальняя дорога». Или сказать так: «Завтра королю либо выпадает ближняя дорога, либо вообще не выпадает дороги».

2) Использование антонима («У него деньжонок мало») вновь приводит к ошибке: денег у него может и вовсе не быть. Спасительное «не» не спасает. Правильное отрицание звучит так: «У него деньжонок мало или совсем нет»

3) Тут все ясно. Любовь либо есть, либо ее нет. Отрицание: «Я денежки не люблю».

1.9. 1) Если контроль за прическами есть, то красить волосы нельзя. Если его отменят, то можно. Но директор возражает против отмены – значит, все же нельзя.

Ответ. Нельзя.

Комментарий. Это утверждение является двойным отрицанием (другими словами, отрицанием отрицания). Истинному утверждению соответствует ложное отрицание и снова истинное двойное отрицание.

2) Если контроль за прическами есть, то красить волосы нельзя. Если решили его запретить, то можно. Если это решение отменить, то снова нельзя. Но директор возражает против отмены – значит, все же можно.

Ответ. Можно.

Комментарий. Здесь отрицание встречается трижды (возражает, отмена, запрет) – т. е. нечетное число раз. Так как пары отрицаний «нейтрализуют» друг друга, то можно считать, что контроль просто отрицается.

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

Ответ 1. Ложно.

Решение 2. Как доказано в первом решении, эта фраза не является истинным высказыванием. А теперь представьте, что фразу «Все критяне лжецы» сказали все критяне одновременно (например, что говоривший – единственный житель острова). Если это ложное высказывание, то все критяне солгали, что делает каждое высказывание истинным.

Ответ 2. Фразу «Все критяне лжецы», сказанную критянином, вообще нельзя считать высказыванием и обсуждать ее истинность.

Комментарий. В задаче изложен парадокс Эпименида – вариант знаменитого парадокса лжеца. Считается, что греческий философ Филит Косский умер от истощения и бессонницы, пытаясь его разрешить. Чтобы не последовать его примеру, мы избрали простейший путь – исключили из рассмотрения утверждения, говорящие о своей истинности. Более сложная точка зрения изложена в главе о парадоксах книги Рэймонда М. Смаллиана «Как же называется эта книга?».

1.11. 1) Верно отрицание: «Сумма двух двузначных чисел может не быть двузначной». В ошибочности формулировки отрицания «Сумма двух двузначных чисел – не двузначное число» поможет убедиться закон исключенного третьего.

2) Утверждение верно. Его отрицание – «Сумма двух четных чисел может не быть четным числом». Ребята скорее всего скажут «Сумма двух четных чисел может быть нечетным числом». Признаем и такую формулировку допустимой, считая заранее известным, что сумма целых чисел – целое число и что все целые числа либо четные, либо нечетные.

3), 4) Для получения отрицания достаточно заменить «можно» на «нельзя» или «невозможно». В пункте 3 верно утверждение. Например, можно сторону 20 разделить на 4 равных части, а сторону 15 – на 5 равных частей и провести через точки деления прямые, параллельные сторонам. В пункте 4 верно отрицание: площадь исходного квадрата нечетна, а предполагаемых частей – четна.

5) Пусть в школе n учеников. Каждый может иметь от 0 до n – 1 друга – всего n вариантов. Но все эти варианты одновременно реализоваться не могут: если у кого-то n – 1 друг (т. е. он дружит со всеми остальными учениками), то никто другой не может вообще не иметь друзей. Поэтому вариантов меньше, чем учеников, и какой-то вариант соответствует хотя бы двум ученикам.

6) Для формулировки отрицания убрать «не» недостаточно. Если уточнить: «Через любое отверстие…», то ясно, что это общее высказывание, к которому отрицание строится так: «В листке из школьной тетради можно прорезать такое отверстие, через которое может пролезть человек». С такими высказываниями мы еще встретимся на втором занятии. Как ни странно, верно именно отрицание. На рис. 21 показано, как вырезать подходящее отверстие. Чем чаще разрезы, тем более длинная и узкая «змейка» будет его ограничивать.

Рис. 21

 

Занятие 2

2.9. 1) Да, могут. Если все грибы съедобны. 2) Да, могут. Если в корзине есть и съедобные, и несъедобные грибы. 3) Да, могут. Если съедобных грибов вообще нет.

2.10. Нет, не является. Эти высказывания вполне могут выполняться одновременно.

2.11. Иллюстрации изображены на рисунке 22. Одинаковый смысл имеют третье и четвертое высказывания.

2.12. Денис не прав. Он путает высказывания «У всех великих людей плохой почерк» и «Все люди с плохим почерком– великие» (см. рис. 23).

2.13. Правду сказали все трое.

Комментарий. «Хотя бы один» означает «Ровно один или больше одного». В данном случае у Зайца «хотя бы один» означает «ровно один», у Волка – «двое», у Лисы – «все трое».

2.14. «Некоторые врачи имеют недостаточный опыт. Каждый врач хоть когда-нибудь ставил неправильный диагноз. Некоторые врачи опаздывают на работу. Некоторые пациенты недовольны лечением. Некоторые пациенты жалуются на бытовые условия. Никто не выздоравливает за один день».

Рис. 22

Рис. 23

2.15. Рыцарь не может сказать «Все мы лжецы», поэтому первый – лжец. Второй сказал правду: «Не все мы лжецы», поэтому он – рыцарь. В комнате больше трех человек (так как первый солгал), но не больше четырех (так как второй сказал правду), то есть ровно четыре. Поэтому третий солгал, и лжецов среди них меньше трех. А двух лжецов мы уже знаем – это первый и третий.

Ответ. Всего в комнате четверо. Лжецов из них двое: первый и третий.

2.16. Заведем на каждого человека досье:

Если у человека есть телевизор, будем писать Т, если нет—T.

Если человек является маляром, будем писать М, если нет—М.

Если человек каждый день купается в бассейне, будем писать Б, если нет—Б.

Например, про человека, не являющегося маляром, имеющего телевизор и каждый день купающегося в бассейне, напишем ТМБ. По этим трем признакам все люди делятся на 8 групп:

1) ТМБ; 2) ТМБ; 3) ТМБ; 4) ТМБ;

5) TМБ; 6) TМБ; 7) TМБ; 8) TМБ.

Условие «Среди людей, имеющих телевизоры, не все являются малярами» означает, что хотя бы в одной из двух групп, третьей и четвертой, есть хотя бы один человек. Условие «Люди, каждый день купающиеся в бассейне, но не являющиеся малярами, не имеют телевизоров» означает, что третья группа людей пуста. Значит, в четвертой группе кто-то есть. И эти люди (или человек) владеют телевизорами, но не каждый день купаются в бассейне.

Рис. 24

Этому решению можно придать более наглядный вид (рис. 24). Вместо таинственных трехбуквенных кодов нарисуем три круга. В один поместим всех владельцев телевизоров, в другой – маляров, в третий – ежедневно посещающих бассейн. Людей, удовлетворяющих всем трем условиям, попросим разместиться на пересечении всех трех кругов, помеченном цифрой 1. Такие люди относятся к первой группе ТМБ. Люди из других групп тоже окажутся на территориях с прежними номерами. Восьмой группе предоставим территорию за пределами всех трех кругов. Дальнейшие рассуждения ничем не отличаются от предыдущей версии.

Ответ. Да, следует.

 

Занятие 3

3.5. Прав, если считать, что марсиан не существует: ведь любое утверждение обо всех элементах пустого множества истинно.

3.6. 1) Нельзя, так как сумма масс 1 + 2 +… + 30 = 31 × 15 – нечетное число. 2) Можно. Пример можно построить, например, так. Сначала сформируем пятнадцать пар гирек веса 31: 1 + 30, 2 + 29 и т. д. Затем возьмем в каждую из трех куч по пять любых пар.

3.7. 1) Предположим, что таблицу заполнить удалось. Если найти сумму чисел во всех строках, то она окажется четным числом, а если во всех столбцах – то нечетным. Но это одно и то же число.

Ответ. Нельзя.

2) Для приведения примера достаточно заполнить первую строку двойками, а остальные – единицами. Заметим, что если заполнить квадрат 3x3 как попало, а остальные числа ставить в соответствии с условием, пример не может не получиться!

Ответ. Можно.

3.8. Нет. Контрпример изображен на рис. 25.

Рис. 25

3.9. Нет. Контрпример: 27 + 15 = 128 + 15 = 143 = 11 · 13.

Комментарий. В настоящее время неизвестно ни одной формулы для вычисления простых чисел.

3.10. Приведем несколько из многих возможных примеров:

1) 1111111212 делится на 12, 1111111125 делится на 15, 1111111432 делится на 16.

2) 111… 1151121792 делится на 128 (все пропущенные цифры – единицы), 222… 22399925 делится на 225 (все пропущенные цифры – двойки).

Ответ. Да.

Комментарий. Для проверки примеров достаточно выполнить деление в столбик. А придумать их можно с помощью признаков делимости: для делимости на 12 надо обеспечить делимость на 3 и 4, для делимости на 15 – на 3 и 5, на 225 – на 9 и 25. Но при сумме цифр 12 или 15 число заведомо кратно 3, а при сумме цифр 225 – кратно 9. Поэтому достаточно с помощью последних цифр обеспечить делимость соответственно на 4, 5 и 25, а затем лишь подобрать нужную сумму цифр. Кроме того, признаки делимости на 2 и 4 можно обобщить: число делится на n-ю степень двойки тогда и только тогда, когда на нее делится число, составленное из n последних цифр исходного. В частности, делимость на 16 проверяется по четырем последним цифрам, а на 128 – по семи. Остальные цифры многозначного числа выбираем любые, лишь бы сумма их была соответственно 16 или 128. Предлагаем читателю самостоятельно составить стозначное число с суммой цифр 144, делящееся на 144.

3.11. 1) Высказывания Б, Г и Д равносильны. Они означают одно и то же: множества дедов и множество волшебников имеют хотя бы один общий элемент (см. рис. 26).

Рис. 26

2) Если А истинно, то истинны и высказывания Б, Г и Д (для них Дед Мороз является подтверждающим примером). А вот В может быть как истинным, так и ложным.

3.12. Подсказка. Верите ли вы в Деда Мороза?

Решение. Парадокс связан с различным пониманием высказывания «Дед Мороз – волшебник».

Первый вариант: существование Деда Мороза считается заранее известным, а в Б утверждается лишь, что он является волшебником. Тогда если верно В, то верно и Б, а если верно Б, то верно и А. В таком случае, действительно, если верно В, то верно и А, никакого контрпримера и противоречия здесь нет: раз мы договорились верить в существование Деда Мороза, то множество дедов не может быть пустым.

Второй вариант: заранее ничего не известно; в Б утверждается, что существует Дед Мороз, являющийся волшебником. Тогда если Б верно, то и А верно. Но утверждать, что если верно В, то верно и Б, нельзя (контрпримером является ситуация, когда множество дедов пусто), поэтому вывод «если верно В, то верно и А» делать тоже нельзя.

3.13. Обсуждение. Что останется, если убрать театрализацию? Утверждение «Если это утверждение истинно, то Дед Мороз существует». Истинно ли оно? Если да, то Дед Мороз существует. Но именно это в нем и сказано, то есть оно истинно. А раз оно истинно, то Дед Мороз существует.

Ответ. Проблема в том же месте, что и в задачах 1.4 и 1.10 первого занятия: классическая логика избегает утверждений, связанных с истинностью их самих: их нельзя считать ни истинными, ни ложными.

 

Занятие 4

4.7. Пригласят.

Комментарий. Изобразим ситуацию с помощью кругов Эйлера (см. рис. 27). Начертим два пересекающихся круга. В первый круг пригласим тех, кто хорошо поет, во второй – всех, кто хорошо танцует. В ансамбль пригласят тех, кто оказался хотя бы в одном из кругов (на рисунке эта область выделена серым), в том числе и Наташу, находящуюся в пересечении кругов.

Рис. 27

4.8. Предположим, Сеня говорит правду. Тогда, согласно его словам, три остальных гнома – вруны. И, тем самым, фраза Бени является правдой. Значит, предположение приводит к противоречию, поэтому Сеня – врун, и его утверждение, что Женя – врун, является ложным. Отсюда заключаем, что Женя говорит правду. Тем самым, Беня – врун, а Веня говорит правду.

Замечание. Фраза Сени «Да оба они вруны» (относительно Бени и Вени) является ложной (несмотря на то, что Беня действительно врун), поскольку Веня – не врун.

Ответ. Женя и Веня.

4.9. Чтобы Аня и Боря были довольны, в пицце должен быть ровно один из ингредиентов: либо помидоры, либо грибы. С учетом вкусов Вани это должны быть грибы.

Ответ. С грибами.

4.10. Решение 1. Верна ровно одна из двух первых подсказок. Поэтому третья и четвертая неверны. Приз в желтом ящике.

Решение 2. Рассмотрим 4 случая. Если приз в синем ящике, то верны подсказки 1 и 4. Если в зеленом – то 1, 3 и 4. Если в красном – то 2 и 4. Если в желтом – то только 2. Так как верна ровно одна подсказка, то приз находится в желтом ящике.

Ответ. Желтый.

4.11. Дед Мороз принес айфоны в квартиры, номера которых кратны 12. А шоколадки – в квартиры, номера которых при делении на 12 дают остатки 4, 6, 8 или делятся нацело. Так как 300 делится на 12 нацело, таких квартир ровно вчетверо больше.

Ответ. Шоколадок больше в 4 раза.

4.12. Д.

4.13. Если на первой табличке написана правда, то и вторая табличка тоже правдива. Но обе таблички одновременно правдивыми быть не могут. Поэтому правда написана на второй табличке, а на первой – ложь. Значит, в первой комнате находится тигр, а во второй – принцесса.

Ответ. Вторую.

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

Ответ. В любую.

4.15. Утверждение «В обеих комнатах находятся принцессы» либо истинно, либо ложно. Если истинно, то в соответствии со словами короля в левой комнате должна находиться принцесса, а в правой – тигр. Но это противоречит истинности утверждения про двух принцесс. Следовательно, оно ложно, и в соответствии со словами короля в левой комнате находится тигр, а в правой – принцесса.

Ответ. В правую комнату.

4.16. Решение 1. Рассмотрим высказывания Никиты и Глеба. Если они оба ложные, то высказывание Антона тоже ложно, а правы только Игорь и Дима. Это противоречит маминому знанию о том, что трое из ее сыновей всегда говорят правду. Если из этих высказываний ложно ровно одно, то ложны и высказывания Игоря и Димы, что также противоречит маминому знанию. Значит, истинны оба первых высказывания (а также и высказывание Димы). По словам Никиты пирог испек Глеб или Игорь. Но по словам Глеба он не пек пирог. Значит, это сделал Игорь.

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

Пусть пирог испек Никита. Тогда Никита солгал (ставим минус в левой верхней клетке), Глеб сказал правду (ставим плюс на клетку ниже), Игорь солгал (ставим минус на клетку ниже), Антон сказал правду (ставим плюс), а Дима солгал (ставим минус).

Заполнив первый столбец, видим, что в этом случае трое братьев сказали неправду, чего быть не может. Считая, что пирог испек Глеб, заполним второй столбец и т. д.

Теперь видно, что пирог испек Игорь.

Ответ. Игорь.

4.17. Решение. Если Маша говорит правду, то Наташа и Гриша умеют сидеть на стуле, поэтому Саша лжет. При этом лгут и Гриша с Наташей, а всего лгут трое.

Если Маша лжет, то Саша может как лгать, так и говорить правду. В первом случае Наташа говорит правду, а Гриша лжет, всего лгут трое. Во втором случае Наташа лжет, лжет и Гриша, и всего снова трое лжецов.

Ответ. Один.

Комментарий. В этой задаче нельзя определить ни кто именно сказал правду, ни кто из детей на самом деле умеет сидеть на стуле. Ясно только, что Гриша солгал.

4.18. Из условия следует, что первым ходил Петя, вторым Вася, а пятой Таня. И что до того, как Таня назвала 15 (вылетев из игры), ни она, ни Петя, ни Вася не ошибались. Предположим, что третий игрок назвал число 3 и вылетел из игры. Тогда 6 досталось Пете (и он сказал «Хоп!»), 9 – Тане (она тоже сказала «Хоп!»), 13 – тоже Тане, но тогда она не могла назвать еще и 15.

Значит, вместо числа 3 игрок сказал «Хоп!», и на первом круге (от 1 до 5) никто не вышел из игры. Поэтому на втором круге очередность ходов не изменилась, и Тане досталось число 10. Если бы четвертый игрок назвал число 9 и вылетел из игры, очередность на третьем круге нарушилась бы, и число 15 не досталось бы Тане. Так как Таня назвала 15, на втором круге (от 6 до 10) снова никто не вылетел. Если бы и от 11 до 14 никто не ошибся, то 20 должен был бы назвать вместо вышедшей из игры Тани Петя, начинавший игру. Но 20 сказал Вася. Кто мог ошибиться, назвав число между 11 и 14? Не Вася, который вместо 12 сказал «Хоп!», а третий игрок, назвавший 13.

Таня и третий игрок вышли. Петя и Вася назвали 16 и 17. Говорить «Хоп!» вместо 18 полагалось четвертому игроку. Если бы он так и сделал, к числу 23 подошла бы Васина очередь. Но это число досталось Пете. Почему? Потому что четвертый игрок назвал 18 и вылетел из игры. Остались Петя с Васей. Когда Петя назвал 23, Вася стал победителем. Он успел сказать «Хоп!» только один раз, вместо числа 12.

Ответ. 1 раз.

 

Занятие 5

5.7. 1) Верно. 2) Обратное высказывание «Если Боря – Женин брат, то Женя – Борин брат» неверно: Женя может быть Бориной сестрой.

5.8. С точки зрения логики правила можно рассматривать как высказывания «А ⇒ Б». Нарушение правила означает ложность этого высказывания. В данном правиле А означает «Житель планеты увидел старшего по рангу». В первых трех случаях А ложно, поэтому высказывание «А ⇒ Б» заведомо истинно. В четвертом случае истинны и А, и Б. А вот в пятом А истинно, а Б ложно.

Ответ. Нарушил правило только Пятый.

Комментарий. Точка зрения плюканского суда может не согласовываться с математической логикой. Но мы спрашивали про вашу точку зрения!

5.9. Первое утверждение верно. Но убедиться в этом не поможет ни один, ни сто примеров многоугольников, требуется общее доказательство. Оно несложно: количество клеточек равно удвоенному количеству доминошек, следовательно, оно четно. Второе утверждение неверно; чтобы это доказать, достаточно привести любой контрпример. Один из них изображен на рисунке справа.

Комментарий. Истинные высказывания в форме следствия доказать на примере нельзя, зато ложные опровергаются с помощью контрпримера. Это неудивительно: ведь следствия могут быть переформулированы как высказывания про всех.

5.10. С точки зрения формальной логики – да, правду. Ведь папоротник не цветет, поэтому утверждение «Человек сорвет цветок папоротника» заведомо ложно. Сложное же высказывание «Если А, то Б» при ложном А истинно независимо от истинности Б.

5.11. Заметим, что из каждого утверждения следует предыдущее (в порядке перечисления). Поэтому если утверждение «Число а делится на 24» верно, то верны и все остальные. Значит, только оно может оказаться единственным неверным из четырех. В качестве примеров подойдут числа, делящиеся на 12, но не делящиеся на 24: 12, 36, 60 и т. д.

5.12. Утверждение «Если на одной стороне карточки написано четное число, то на другой – гласная буква» является ложным лишь в одном случае: если на одной стороне карточки четное число, а на другой – согласная буква. Поэтому надо перевернуть 2 карточки: с числом 4 (на обороте должна быть гласная буква) и с буквой Б (на обороте должно быть нечетное число).

Ответ: 2 карточки.

5.13. Решение 1. В (1) сказано, что если не будет ветра, то будет пасмурная погода без дождя. Но в (3) сказано, что пасмурной погоды без дождя не будет. Значит, будет ветрено. По условию (2) в случае дождя ветра не было бы. Значит, дождя не будет. А по условию (3) и в случае пасмурной погоды не было бы ветра. Значит, будет солнечно.

Ответ. Будет солнечно, ветрено, но без дождя.

Комментарий. Разобравшись, в каком порядке использовать условие, удалось решить задачу коротко. Можно прийти к ответу и менее творчески, методом полного перебора.

Решение 2. Выпишем все 8 возможных (в этой задаче) типов погоды: СВД, СВД, СВД, СВД, СВД, СВД, СВД, СДД. В этой записи С означает солнце, В – ветер, а Д – дождь; если буква зачеркнута, то такого не будет. Например, СВД означает погоду пасмурную, безветренную и с дождем. Вычеркнем сочетания, противоречащие первому прогнозу: СВД, СВД, СВД. Остались СВД, СВД, СВД, СВД, СВД. Вычеркнем из них противоречащие второму прогнозу: СВД, СВД. Остались СВД, СВД, СВД. Наконец, вычеркнем СВД и СВД, противоречащие третьему прогнозу. Остался прогноз СВД: солнечно, ветрено, но без дождя.

5.14. Примеры Шляпы и Сони действительно показывают разницу между «А ⇒ Б» и «Б ⇒ А». Чтобы в этом убедиться, можно каждую фразу построить более формально, например, «Если я что-то ем, то я это вижу» и т. п.

Пример Зайца можно понимать по-разному. Первое его высказывание может означать «Если я что-то учу, то я этого не знаю» (А ⇒ «не Б»), тогда второе следует понимать как «Если я что-то знаю, то я этого не учу». (Б ⇒ «не А»). Но оба эти высказывания истинны при одном и том же условии: А и Б не должны выполняться одновременно. А это значит, что высказывания «А ⇒ „не Б“» и «Б ⇒ „не А“» равносильны. Иное возможное толкование первого высказывания «Если я чего-то не знаю, то я это учу» («не А» ⇒ Б) соответствует пониманию второго как «Если я чего-то не учу, то я это знаю» (не Б ⇒ А). Эти высказывания также равносильны, поскольку оба оказываются истинными во всех случаях, кроме одного: А и Б оба ложны. Итак, с формальной точки зрения высказывания «Я учу то, чего не знаю» и «Я знаю то, чего не учу» действительно означают одно и то же, и пример Зайца неубедителен. А с точки зрения здравого смысла? «Я учу то, чего не знаю» говорит о любознательности, а «Я знаю то, чего не учу» – о глупой самонадеянности. В чем секрет? Во временах глаголов! «Я учу то, чего не знаю» мы понимаем как «Я сейчас учу то, чего не знал раньше», а «Я знаю то, чего не учу» – как «Я сейчас знаю то, чего не учил раньше». Никаких одинаковых простых высказываний А и Б не наблюдается, и говорить о равносильности составных нет причин.

Комментарий. В оригинальном английском тексте высказывание Зайца, связанное со свободным употреблением времен глаголов в русском языке, отсутствует. Нет его и в переводах на русский язык В. Набокова и Н. Демуровой.

 

Занятие 6

6.6. Нет.

6.7. 1) Пусть у меня есть единственный друг Петя. Он болеет за «Спартак», но не занимается спортом. А у «Спартака» кроме Пети есть еще один болельщик, Вася, который спортом занимается. Тогда оба условия верны, а вывод – нет.

2) Пусть есть два паровоза, зеленый и красный. Зеленый является кочаном капусты, но не играет на рояле. А красный, наоборот, кочаном капусты не является, зато на рояле играет. И никаких других кочанов капусты, кроме зеленого паровоза, на свете нет. Тогда оба условия верны, а вывод – нет.

6.8. 1) См. рис. 28.

Рис. 28

2) См. рис. 29.

Рис. 29

6.9. Первое рассуждение верное, так как все англичане входят в круг любителей пудинга, а французы находятся вне его. Второе неверно. Чтобы в этом убедиться, представьте себе, например, что никто вообще не достоин славы.

6.10. 1) Вывод сделать нельзя. 2) Некоторые горные кручи не являются заборами. 3) Джон – не гусеница. 4) Вывод сделать нельзя. 5) Музыка, не вызывающая колебаний воздуха, не стоит того, чтобы за нее платили деньги.

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

Ответ. Вывод неверен.

 

Занятие 7

7.7. Утверждение «Если собаки рядом нет, то кот не шипит» противоположно обратному к утверждению «Если кот шипит, то рядом собака». Поэтому они равносильны, и достаточно было бы произнести любое из них.

Ответ. Сказал.

7.8. 1) Неверно, про Петино поведение при несделанных уроках никаких данных нет. Он мог, скажем, поднять руку, чтобы задать вопрос. 2) К сожалению, верно. Это можно доказать от противного: если бы Петя был готов к уроку, он бы поднял руку.

7.9. Решение 1. Предположим противное: числа на концах любого ребра отличаются не более чем на 2. Рассмотрим вершину, в которой расположено число 1. В соседних с ней вершинах могут располагаться лишь 2 и 3. Но у каждой вершины куба есть три соседних. Полученное противоречие доказывает, что предположение неверно, и числа на концах хоть какого-нибудь ребра должны отличаться не менее чем на 3.

Решение 2. Предположим противное: числа на концах любого ребра отличаются не более чем на 2. От одной вершины до любой другой вершины можно добраться по одному, двум или трем ребрам. Поэтому числа в вершинах куба отличаются друг от друга не более чем на 6. Однако среди них есть 1 и 8, отличающиеся на 7. Полученное противоречие доказывает, что предположение неверно, числа на концах хоть какого-нибудь ребра должны отличаться не менее чем на 3.

7.10. Решение 1. Предположим, что нет двух друзей, которые послали открытки друг другу. Тогда каждый мог получить не более четырех открыток – только от тех, кому сам не посылал. И даже если все открытки дошли, каждый получил меньше открыток, чем послал. Поэтому и общее число отправленных открыток больше числа полученных. Противоречие.

Решение 2. Предположим, что нет двух друзей, которые послали открытки друг другу. Тогда послано не более 10 · 9: 2 = 45 открыток, но по условию их было послано 5*10 = 50. Противоречие.

7.11. Допустим, что это возможно. Пусть сумма чисел, стоящих в концах отрезков, равна А, сумма чисел, расположенных в серединах отрезков, равна В, а сумма трех чисел вдоль каждого отрезка равна С. Ясно, что А + В = 0 + 1 + 2 +.. + 9 = 45. Каждая концевая точка принадлежит ровно трем отрезкам, а все середины различны. Поэтому, сложив суммы чисел на всех шести отрезках, получим: ЗА + В = 6С. Отсюда 2А + 45 = 6С. Получили противоречие, так как слева нечетное число, а справа четное.

Ответ. Нельзя.

7.12. Вничью игра закончиться не может. Это означает, что ровно у одного из игроков есть выигрышная стратегия. Предположим, что такая стратегия есть у второго игрока. Долька, находящаяся в правом верхнем углу, съедена в любом случае после первого хода. Если у второго есть выигрышная стратегия, то у него есть выигрышный ответный ход на ход первого, состоящий в поедании только правой верхней дольки. Но этот выигрышный ход первый может с тем же успехом сделать сам с самого начала, а далее воспользоваться выигрышной стратегией второго.

7.13. Обсуждение. Задача кажется неприступной. Прежде чем нащупать «узкое место», хочется поэкспериментировать. Но как тут экспериментировать, когда секторов 25, да еще и порядок произвольный? А если секторов поменьше? Если секторов три, их все посетить не удастся, это доказывается коротким перебором. Если четыре, то их все можно посетить. Если пять – снова не удается. Здесь полный перебор уже затруднителен, зато видны две особенности сектора номер пять: если попадешь в пятерку, оттуда никуда не уйдешь; если удается пройти почти все числа, то именно пятерка всегда остается. Интересно, почему?

Решение. Предположим, что кузнечик побывал во всех секторах. Тогда сектор с номером 25 был последним, так как из него кузнечик не сможет переместиться в иной сектор. До этого кузнечик не мог побывать дважды в одном секторе, иначе бы его путь зациклился, и в 25-й сектор он бы не попал. А побывав во всех секторах по разу, кузнечик переместился бы на 1 + 2 +… + 24 = 300 секторов, то есть на число, кратное 25. Значит, он начал свое путешествие в 25-м секторе, что невозможно.

7.14. 1) Предположим, что после построения по росту Вася выше стоящего сразу за ним Никиты более чем на 10 см. Назовем Васю и стоящих перед ним мальчиков высокими, а Никиту и стоящих после него мальчиков низкими. Разница в росте между любым высоким и любым низким мальчиком больше 10 см. Но при первоначальном построении, идя вдоль строя от Васи к Никите, мы на каком-то шаге перейдем от высокого к низкому. Эти два мальчика стояли рядом, поэтому разница в росте между ними не превышает 10 см. Противоречие.

2) Пусть мальчики и девочки построены в пары в порядке убывания роста. Предположим, что в одной из пар мальчик Ваня выше девочки Маши более, чем на 10 см. Тогда рост каждого мальчика, стоящего до Вани, отличается от роста каждой девочки, стоящей после Маши, еще сильнее. Поэтому при первом построении каждый из этих мальчиков, включая Ваню, мог стоять только с кем-то из девочек, стоящих перед Машей, но таких девочек на одну меньше, чем требуется. Противоречие. Если Маша выше Вани, рассуждения аналогичны.

7.15. Слово «надо» употребляется в разных смыслах. Сначала подразумевается «нужное количество ленивых учеников», а потом – «нужное количество прилежных учеников».

 

Занятие 8

8.6. Обсуждение. Пусть А: «У Винни-Пуха хорошее настроение»; Б: «Винни-Пух хорошенько подкрепился». В какую строчку таблицы истинности надо посмотреть? Ответ. Не прав.

8.7. Истинны высказывания в пунктах 1, 3, 4, 5, 7. Ложны высказывания 2, 6, 8.

8.8. Все три высказывания означают, что некузявых ляпусиков не бывает.

Ответ. Равносильны.

8.9. Пусть Д спит. Тогда А и Г спят (из 5). Тогда Б спит (из 1), поэтому В не спит (из 3). Но это противоречит 4.

Значит, Д не спит. Тогда спят Г (из 2) и В (из 4), а Б не спит (из 3). Поэтому А не спит (из 1).

Ответ. В и Г.

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

Пусть при любой рассадке по кругу найдутся два мальчика рядом. Рассмотрим произвольную рассадку и занумеруем детей по кругу по часовой стрелке. А затем посадим детей в таком порядке: 1, 3, 5, 7, 9, 11, 13, 15, 17, 2, 4, 6, 8, 10, 12, 14, 16. По условию после этого найдутся два мальчика рядом. Но раньше они сидели через одного, т. е. в исходном положении был гость, сидевший между ними.

Пусть при любой рассадке по кругу найдется гость, сидящий между двумя мальчиками. Докажем от противного, что мальчиков больше, чем девочек. Действительно, если бы девочек было больше, детей можно было бы рассадить так: ДДГГДДГГДДГГДДГГД, где буква Д означает девочку, а буква Г – гостя любого пола, и никто бы не сидел между двумя мальчиками.

8.11. 1) Всего существует 6 теорем указанного вида. Если дать их все, то последняя будет следовать из предыдущих. А 5 можно дать в таком порядке: 1 ⇒ 2, 1 ⇒ 3, 2 ⇒ 3, 3 ⇒ 2, 3 ⇒ 1.

2) Всего существует 12 таких теорем. Как отмечено в предыдущем пункте, с участием утверждений 1, 2 и 3 нельзя давать все 6 возможных теорем. Без ограничения общности можно исключить теорему 2 ⇒ 1. Но с участием утверждений 2, 3 и 4, а также 1, 3 и 4 тоже нельзя давать все 6 возможных теорем. Если пытаться решить обе проблемы исключением лишь одной теоремы, исключать надо 3 ⇒ 4 или 4 ⇒ 3. В любом из случаев остается цепочка из восьми теорем 1 ⇒ 3 ⇒ 2 ⇒ 4 ⇒ 1, из которой придется исключить как минимум одну теорему, и останется не более 9 теорем. Пример на 9 теорем: 1 ⇒ 2, 1 ⇒ 3, 1 ⇒ 4, 2 ⇒ 3, 2 ⇒ 4, 3 ⇒ 4, 4 ⇒ 3, 4 ⇒ 2, 4 ⇒ 1.

3) Пример на  теорем:

1 ⇒ 2, 1 ⇒ 3…, 1 ⇒ n,

2 ⇒ 3, 2 ⇒ > 4…, 2 ⇒ n,

n — 1 ⇒ n,

n ⇒ n − 1, n ⇒ n − 2…, n ⇒ 1.

Доказательство максимальности удобно изложить на языке графов. Будем считать утверждения вершинами, а теоремы – ориентированными ребрами. Оставим только ребра, ориентированные в обе стороны. Если бы они образовали цикл, то последняя доказанная в этом цикле теорема следовала бы из предыдущих теорем цикла. Значит, циклов нет. Тогда «двойных» ребер – не более n — 1, поэтому всего доказано не более  теорем.

Ответ. 1) 5; 2) 9; 3)

 

Занятие 9

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

Ответ. 6, 8, 10.

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

Ответ. Джон – второй.

Комментарий. Почему эта задача является метаголоволомкой? Потому что важным условием является тот факт, что судья смог определить, кто из братьев Джон.

9.6. Рассмотрим четыре случая:

1) оба рыцари;

2) говоривший – рыцарь, а его спутник – лжец;

3) говоривший – лжец, а его спутник – рыцарь;

4) оба лжецы.

Во втором случае на первый вопрос был бы ответ «Нет», а в остальных – «Да». Поскольку путешественник не смог сделать вывод, второй случай исключен. На второй вопрос ответ «Да» был бы в первом и третьем случае, и различить их нет никакой возможности. А ответ «Нет» – во втором и четвертом случаях. Путешественник уже исключил второй случай, остается только четвертый.

Ответ. Двух лжецов.

9.7. Всех стоящих в кругу жителей деревни можно мысленно разбить на группы стоящих подряд правдивых людей и группы стоящих подряд лжецов (возможно, состоящие из одного человека). Крайние справа в своих группах назовут своих правых соседей лжецами, а остальные жители назовут своих правых соседей правдивыми. Из ответов всех жителей следует, что выполняется один из двух вариантов: истинный и соответствующий ему «с точностью до наоборот». Если истинная доля лжецов равна х, то во втором варианте она равна 1-х. Так как путешественник смог определить долю лжецов, то х = 1 – х, откуда х = 1/2.

Ответ. 1/2.

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

Ответ. Два рыцаря.

9.9. Оба загадали делители числа 2002 (иначе кто-то понял бы, что 2002 – сумма загаданных чисел, и определил бы второе число). Однако, даже зная, что Саша загадал делитель, Маша не может исключить, что 2002 – сумма. Но сумма делителей равна 2002 только в случае 1001 + 1001 (другие делители равны 2002 либо меньше 1001). Значит, Маша загадала 1001 (а Саша – 2 или 1001, и тогда оба действительно не могли узнать числа друг друга).

 

Ответ. 1001

9.10. 1) Василиса может найти последнюю цифру суммы цифр на своих карточках. Прибавив к ней 7, она узнает последнюю цифру суммы цифр на всех карточках, кроме карточки Бабы-Яги. Остается вычесть результат из 5 (или из 15), так как сумма цифр на всех карточках равна 45.

Ответ. Знает.

2) Выпишем все суммы четырех ненулевых чисел, оканчивающиеся на 7:

1 + 2 + 5 +9, 1 + 2 + 6 +8, 1 + 3 + 4 +9, 1 + 3 + 5 +8,

1 + 3 + 6 + 7, 1 + 4 + 5 + 7, 2 + 3 + 4 + 8, 2 + 3 + 5 + 7,

2 + 4 + 5 + 6, 3 + 7 + 8 + 9, 4 + 6 + 8 + 9, 5 + 6 + 7 + Э.

Какая бы цифра ни была у Бабы-Яги, среди выписанных сумм найдутся две, не содержащие этой цифры. Каждая из них могла получиться из цифр Ивана, а Василисе достались бы остальные цифры.

Ответ. Не знает.

3) Пусть, скажем, у Бабы-Яги карточка 1. Тогда цифры Ивана образуют одну из сумм, не содержащих 1:

2 + 3 + 4 +8, 2 + 3 + 5 +7, 2 + 4 + 5 +6,

3 + 7 + 8 +9, 4 + 6 + 8 + 9, 5 + 6 + 7 + 9.

Для любой цифры, отличной от 0 и 1, среди выписанных найдется как сумма, содержащая эту цифру, так и сумма, не содержащая ее. Аналогично разбираются случаи всех остальных карточек Бабы-Яги.

Ответ. Не может.

Комментарий 1. Если бы Иван назвал вместо 7 любую другую цифру, ответы и решения остались бы прежними с точностью до конкретных выписанных сумм.

Комментарий 2. Разобранный пример показывает возможность вслух сообщить информацию так, чтобы партнер, владеющий дополняющей информацией, понял все, а случайный слушатель – ничего. Подобным образом происходят электронные платежи – банк должен узнать клиента, при этом доступ к чужому счету для жуликов должен быть максимально затруднен. Доказательствами без разглашения занимается прикладная криптография.

9.11. Участник А не может быть мирным жителем, так как в этом случае он ничего не знал бы про Д. Если бы Б был мирным жителем, то к моменту своего высказывания он знал бы только то, что А не мирный житель, и свою роль в игре. Этого недостаточно, чтобы утверждать, что Д – мафиози. Если В – мирный житель, то у него нет оснований исключать, что А и Б – мафиози, а Д – комиссар, и тогда Д знает, кто он. Поэтому и В не мирный житель. Получается, что мирные жители – Г и Д. Они оба это к моменту высказывания Г понимают, так что Г говорит правду. Участник Б лжет, поэтому он – мафиози. Кто из А и В комиссар, а кто второй мафиози, определить невозможно, оба варианта не противоречат высказываниям всех игроков.

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

 

Занятие 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. Клара знает, что Шерлок знает, что Клара знает, что Шерлок знает, что Фридрих знает, что Карл украл кораллы (и благополучно скрывается вместе с Фридрихом).