Дополнительные задачи
Д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) Я не видел медведя или он видел меня.
3) Я боюсь львов или крокодилов.
4) Лошадь не заблудилась и ее не засыпало снегом.
5) Я не отправился в разведку ни на коне, ни на ядре.
Д12. Третья дверь может вести только в учительскую. Значит, за дверью с табличкой «Спортзал» не спортзал и не учительская, т. е. столовая.
Ответ. В столовую.
Д13. Если Руссо прав, то Жан и Жак оба лгут, чего не может быть (вспомните, что говорит Жан). Значит, Руссо лжет. Поэтому Жак прав. А тогда Жан лжет.
Ответ. Правду говорит только Жак.
Д14. Если А – рыцарь, то ОБЕ части его высказывания правдивы. Но в одной из них сказано, что он лжец. Противоречие. Значит, А – лжец. Первая часть его высказывания истинна, поэтому ложной должна быть вторая часть (тогда и все высказывание ложно). Поэтому Б тоже лжец.
Ответ. Оба лжецы.
Д15. Решение 1. Все трое рыцарями быть не могли (в таком случае они не стали бы называть друг друга лжецами).
Два рыцаря и один лжец тоже быть не могли (в таком случае оба утверждения ложны, а лжец только один).
Два лжеца быть могли. Например, Ох и Ух, которые и сделали ложные утверждения, так как Ах – рыцарь.
Все трое лжецами быть не могли, так как в таком случае оба утверждения истинны.
Решение 2. Если оба ответа ложны, то среди троих двое солгали и есть хотя бы один рыцарь, то есть лжецов ровно двое. Если же среди ответов есть верный, то его дал рыцарь, а двое им названных – лжецы. Пример: рыцарь Ух сказал, что Ах и Ох лжецы.
Ответ. Двое.
Д16. Если бы А был лжецом, его высказывание оказалось бы истинным. Поэтому он рыцарь. В таком случае он говорит правду, и Б – лжец.
Комментарий. Задача напоминает парадокс лжеца: здесь также сказанное имеет отношение к его истинности. Но наличие второго островитянина Б превращает парадокс в задачу с однозначным ответом.
Д17. Среди них нет рыцарей, и оба они не могут быть лжецами, потому что тогда они бы сказали правду. Значит, либо оба они хитрецы, либо один хитрец, а другой лжец.
Д18. Решение 1. Посмотрим, кто может быть рыцарем. Это не А, называющий себя хитрецом. И не Б, так как в этом случае никто не мог бы быть лжецом. Значит, рыцарь – В. Он говорит правду, поэтому Б – хитрец. Тогда А – лжец. Заметим, что высказывание хитреца Б ложно.
Решение 2. Предположим, что А сказал правду и он действительно хитрец, тогда В солгал и он лжец. В этом случае Б должен быть рыцарем. Но его высказывание неверно, так как В никогда не говорит правду. Получили противоречие. Предположим теперь, что А солгал, тогда он лжец, и, следовательно, высказывание Б ложно. Значит, Б – солгавший хитрец, а В – рыцарь, что подтверждается его верным высказыванием.
Ответ. А – лжец, Б – хитрец, В – рыцарь.
Д19. Высказывания Ромы и Коли противоположны, поэтому истинно ровно одно из них. Это же можно сказать о высказываниях Маши и Нины. Кроме того, из высказывания Саши следует, что либо он говорит правду, либо Аня. Значит, из высказываний Ани и Саши истинно тоже ровно одно. Поскольку истинных высказываний ровно три, оставшиеся высказывания (Володи, Егора и Олега) ложные. Окно разбила Нина.
Ответ. Нина.
Д20. В понедельник, вторник, среду, пятницу и воскресенье.
Д21. Если в думе есть хоть один рыцарь, то всего в ней четное число депутатов, и спикер – лжец. А если нет ни одного рыцаря, то он тем более лжец!
Ответ. Лжец.
Д22. Формально: см. третью строку таблицы истинности высказывания «А ⇒ Б». Неформально: у волка есть и другие причины для радости.
Ответ. Нет.
Д23. Достаточно привести любой пример, в котором все три высказывания верны, но Иван не является братом Марьи. Иван может приходиться Марье отцом, дядей, племянником и т. д.
Ответ. Нет.
Комментарий. К ошибочному выводу можно было бы прийти, перепутав в первом высказывании причину и следствие и ошибочно заменив его на обратное: «Если Иван и Марья – родственники, то Иван – брат или сын Марьи».
Д24. Если этот житель рыцарь, то он сказал правду, и его друг действительно лжец. А если он сам лжец? Тогда любое утверждение, начинающееся со слов «Если я рыцарь…» оказывается истинным и просто не может быть произнесено лжецом!
Ответ. Да; он – рыцарь, а его друг лжец.
Д25. Если у Волкова нет собаки, то ее нет и у Львова, тогда собаку держит Щукин. В таком случае у Волкова кошка, а у Львова рыбки. Но по последнему условию если у Львова рыбки, то у Щукина кошка. Полученное противоречие показывает, что у Волкова есть собака. Если бы кошка жила у Щукина, то у Волкова был бы аквариум. Значит, кошку держит Львов, а рыбок – Щукин.
Ответ. У Львова кошка, у Волкова собака, а у Щукина рыбки.
Д26. Из третьего и четвертого условий Нуф-Нуф и Наф-Наф либо оба виновны, либо оба невиновны. Поэтому по второму условию Ниф-Ниф невиновен. Поэтому и Нуф-Нуф с Наф-Нафом невиновны (из пятого условия). Итак, никто челюсть украсть не мог, а обвинение в лжесвидетельстве Шерлок Холмс предъявит Серому волку.
Д27. Иа-Иа не мог участвовать в краже одновременно с Тигрой (так как им требуется различное число соучастников). Поэтому если Тигра виновен, то вместе с ним был либо Пятачок (а тогда и Винни-Пух), либо только Винни-
Пух. Если виновен Иа-Иа, то два его соучастника – Пятачок и Винни-Пух. А если ни Тигра, ни Иа-Иа ни при чем, то мед украл либо Пятачок (а тогда он был вместе с Винни-Пухом), либо только Винни-Пух.
Ответ. Винни-Пуха.
Д28. 1) Приведем контрпример: —5; 2; 2; 2; —5; 2; 2; 2; -5.
Ответ. Нет.
2) Возьмем произвольные четыре числа. Их сумма положительна, поэтому положительно хотя бы одно из этих чисел. Возьмем его, а остальные восемь чисел разобьем на две четверки чисел, сумма которых положительна.
Ответ. Да.
Комментарий. Для обоснования отрицательного ответа в первом случае достаточно одного контрпримера. Для обоснования положительного ответа во втором случае необходимо доказательство.
Д29. 1) Ложно. Можно сделать лишь вывод о том, что некоторые улитки любят кошек.
2) Истинно.
Д30. 1) Устрица не является ископаемым животным.
2) Со мной никогда не случалось этого.
3) Вывод сделать нельзя.
4) Дети не управляют крокодилами.
5) Ни один из твоих подарков не сделан из олова.
Д31. Из условия следуют только два утверждения – второе и четвертое.
Д32. Это задача-шутка. Первый вывод в бытовой речи допустим, хотя автор «Мертвых душ» – не единственный носитель фамилии Гоголь, и нельзя исключать наличие портрета другого Гоголя. Второй вывод явно неверен. Отличие в употреблении неопределенного местоимения «какой-то». Фразам с неопределенными местоимениями в логике соответствуют не высказывания, а предикаты; их серьезное изучение выходит за рамки данной книжки.
Д33. Если бы такое число существовало, то вдвое меньшее число тоже было бы рациональным и положительным.
Ответ. Нет.
Д34. Предположим, что заработок Папы Карло каждый месяц был целым. Перечислим месяцы в порядке возрастания заработка. Тогда за первый месяц Папа Карло заработал не менее нуля золотых, за второй не менее одного…, за двенадцатый не менее одиннадцати. Всего он заработал не менее 0 + 1 + 2 +.. + 11 = 66 золотых, что противоречит условию. Значит, предположение неверно, и какой-то из заработков не был целым.
Д35. На круге чередуются группы подряд идущих четных чисел с группами подряд идущих нечетных. Предположим, что нет двух четных чисел рядом. Если в каждой «четной» группе – ровно одно число, то таких групп 1005. Значит, и «нечетных» групп 1005, то есть столько, сколько нечетных чисел. Тогда и в каждой «нечетной» группе – по одному числу, то есть четные и нечетные числа строго чередуются. Но это значит, что либо каждое четное число больше обоих соседних нечетных, либо каждое четное число меньше обоих соседних нечетных. В первом случае не найдется места для числа 2, а во втором – для числа 2010. Противоречие.
Д36. Обсуждение. С чего начать, ясно. Надо предположить, что разрезание возможно, и прийти к противоречию. Но к какому? Подумаем, в чем сложность разрезания: надо куда-то деть круглые куски с границы круга. Для этого нужно вырезать подходящие круглые дополнения, но при их вырезании получится что? Тришкин кафтан! Остается только толково пояснить, чем отличаются «плохие» круглые участки от «хороших».
Решение. Предположим, что такое разрезание возможно. Рассмотрим кусочки, составляющие квадрат. Выберем из них все те, в границу которых входят дуги, которые составляли границу круга или являются дугами того же радиуса г. В квадрате суммы длин этих дуг, к которым кусочки примыкают «изнутри» и «снаружи» (с вогнутой и выпуклой сторон), равны. А в круге разность между теми и другими должна равняться длине окружности 2 кг. Противоречие.
Ответ. Нельзя.
Д37. Возьмем произвольный бюллетень из 11-й урны. Пусть там написаны десять фамилий: Первый, Второй, Третий…, Десятый. Предположим, что ни для одной из урн нет кандидата, фамилия которого написана во всех бюллетенях из этой урны. Тогда в первой урне найдется бюллетень без упоминания Первого, во второй найдется бюллетень без Второго и т. д. Возьмем 10 таких бюллетеней. Вместе со взятым вначале бюллетенем из 11-й урны получим набор, противоречащий условию задачи.
Д38. Каждым из двух качеств (ловкость и везение) Джо может обладать или не обладать. Рассмотрим все 4 варианта. Первый: Джо ловкач и ему везет. Тогда верны высказывания 1 и 5. Второй: Джо ловкач и ему не везет. Тогда верны высказывания 1, 2, 4, 6. Третий: Джо не ловкач и ему везет. Тогда верны высказывания 3, 4 и 6. Четвертый: Джо не ловкач и ему не везет. Тогда верны высказывания 2, 4 и 5. Наибольшее число высказываний верно во втором случае.
Ответ. 4.
Д39. Годятся различные вопросы. Например, можно спросить: «Правда ли, что у тебя золотых монет больше, чем у Алеши Поповича?» Если у Ильи Муромца две золотые монеты, он скажет «Да», если обе монеты у Ильи серебряные, то «Нет», а если ему достались разные монеты, то он ответит «Не знаю».
Другой вариант: «Досталась ли Алеше хотя бы одна золотая монета?». Если у Ильи обе монеты серебряные, он ответит «Да», если обе золотые, он ответит «Нет», а если одна золотая, а другая серебряная, он ответит «Не знаю».
Возможны также вопросы:
– Правда ли, что одному из двух других богатырей достались две серебряные монеты?
– Верно ли, что два других богатыря получили хотя бы по одной золотой монете каждый?
– Если я заберу у тебя одну монету и дам вместо нее золотую, станет ли у тебя больше золотых?
Д40. Если бы первый назвался лжецом, мудрец понял бы сразу, что тот хитрец. А вот рыцарем себя мог назвать любой из них. И в этом случае даже после ответов остальных мудрец не смог бы определить, кто первый на самом деле. Действительно, он мог бы и вправду быть рыцарем (лжец и хитрец могли назвать его лжецом и хитрецом в любом порядке). Но мог бы быть и лжецом (при этом рыцарь назвал бы его лжецом, а хитрец мог и хитрецом). А мог и хитрецом (рыцарь назвал бы его хитрецом, а лжец – лжецом).
Если же первый назвался хитрецом, то сразу можно понять только, что он не рыцарь. Поэтому не рыцарь и тот, кто назвал его рыцарем. Кто же рыцарь? Тот, кто назвал первого лжецом. Поэтому первый – лжец.
Ответ. Лжец.
Д41. Возможны три случая:
1) А – рыцарь;
2) А – шпион, и он сказал правду;
3) А – шпион, и он солгал.
В первом случае А скажет «да», во втором – «нет», в третьем– «да». Поэтому по его ответу можно делать вывод только во втором случае. Итак, А – шпион, зачем-то сказавший правду.
Д42. 1) Если бы на вопрос «Вы шпион?» А ответил «нет», то он мог бы быть рыцарем или шпионом, а если «да», то он мог бы быть лжецом или шпионом. В первом случае то, что А сказал правду про В, не позволило бы судье понять, кто В, а во втором позволило бы. Значит, А сказал «да», и он шпион.
Ответ. А – шпион.
2) Мы уже выяснили, что А сказал «Да». Если бы Б сказал «Нет», то судья не понимал бы еще, что В – не шпион, а должен был допускать три возможности: 1) А – лжец, Б – рыцарь, В – шпион; 2) А – лжец, Б – шпион (сказавший правду), В – рыцарь; 3) А – шпион (сказавший правду), Б – лжец, В – рыцарь. Но судья понял, что В – не шпион. Значит, Б тоже сказал «Да». В таком случае судья должен допускать две возможности: 1) А – лжец, а Б – шпион (солгавший); 2) А – шпион (сказавший правду), а Б – рыцарь. В обоих случаях он действительно понимает, что В – не шпион. А когда А сказал, что В – не шпион, судья понимает и то, что А – не лжец, и реализуется второй из двух случаев: А – шпион, Б – рыцарь, В – лжец.
Ответ. «Да».
Д43. Обсуждение. Чтобы лучше почувствовать задачу, попробуем для начала действовать наугад. Предположим, например, что дураков и умных в думе по 100. Тогда умные дадут ответы от 98 до 100 (в зависимости от скромности и от того, кто именно уехал), а все дураки скажут «Один», и премьер-министр легко отличит умного от дурака. Почему же он не смог понять ответ? Потому что умные отвечали так же, как дураки, то есть их было мало.
Решение. Заметим, что все дураки дадут ответ: «Один». Если бы умных в думе было три или больше, то они дали бы ответ: «Два (или больше)» и премьер-министр всё бы понял. Значит, умных могло быть 0, 1 или 2.
Рассмотрим все эти случаи. Если умных не было, то все сказали: «Один». Если был один умный уверенный, то он тоже сказал: «Один», и ситуация неотличима от предыдущей. Если был умный скромный, то он сказал: «Ни одного», и эта ситуация отличима. Если было два скромных умных, они сказали: «Один», и ситуация неотличима от предыдущей. Если бы было два уверенных умных, они сказали бы: «Два», и ситуация была бы отличима. Наконец, если бы были один уверенный и один скромный умный, то уверенный сказал бы: «Два», и ситуация также была бы отличима.
Таким образом, возможны три неразличимых варианта: нет умных, один уверенный умный и два скромных умных. Во всех этих случаях все участники опроса ответят: «Один».
Посмотрим, какие ответы даст опоздавший думец в каждой из этих ситуаций в зависимости от его ума и скромности:
Видно, что ответы «1» и «2» встречаются в нескольких клетках, т. е. такие ответы не помогли бы различить ситуации. Зато ответы «О» и «3» встречаются в таблице по одному разу и позволяют сделать однозначный вывод. Значит, опоздавший дал один из этих ответов. В первом случае в думе один умный, во втором – три.
Ответ. 1 или 3.
Д44. 1) Занумеруем карты от 0 до 6. Можно считать, что у Гриши карты 1, 2 и 3. Пусть он скажет: «У меня либо набор 1, 2, 3, либо набор 4, 5, 6». Поскольку у Леши на руках как минимум две карты из набора 4, 5, 6, он понимает, что у Гриши набор 1, 2, 3, и знает, какая карта спрятана. Теперь Леша должен сообщить Грише свои карты. Возможны два случая.
1. У Леши набор 4, 5, 6 (а спрятана карта 0). Леша говорит: «У меня либо набор 4, 5, 6, либо 1, 2, 0».
2. У Леши другой набор, скажем, 4, 5, 0 (а спрятана карта 6). Леша говорит: «У меня либо набор 4, 5, 0, либо 1, 2, 3».
В обоих случаях названный Лешей «не свой» набор пересекается с Гришиным как минимум по двум картам, поэтому Гриша тоже узнает, какой на самом деле набор у Леши. Докажем, что Коле ничего не ясно. Действительно, и в том, и в другом случае названо три набора карт: А, В и С. Наборы В и С пересекаются по двум картам, Гриша сказал: «У меня либо А, либо В», Леша сказал: «У меня либо А, либо С». Это означает, что либо у Гриши набор А, а у Леши – С, либо у Гриши – В, а у Леши – А. Поэтому три карты из набора А и две карты из пересечения наборов В и С могут оказаться как у Гриши, так и у Леши (в нашем примере это карты 1, 2, 3, 4 и 5). А из остальных двух карт наборов В и С (в нашем примере 6 и 0) одна закрытая, другая – у одного из игроков. Поэтому местоположение никакой из карт Коля вычислить не может.
2) Заметим, что предыдущий способ не работает: зная закрытую карту, Коля может всё определить.
Пусть Гриша занумерует карты числами от 0 до 6 (и объявит об этом вслух). Затем пусть Гриша и Леша по очереди назовут остатки от деления суммы номеров своих карт на 7. Тогда они узнают расклад: ведь остаток суммы Гриши плюс остаток суммы Леши плюс номер спрятанной карты должны давать 0 + 1 + 2 + 3 + 4 + 5 + 6 = 0 (mod 7). Так, например, если у Леши карты 1, 3, 4, а Гриша назвал остаток 4, то спрятана карта —4 – (1 + 3 + 4) = 2 (mod 7), значит, у Гриши карты 0, 5, 6.
Проверим, что Коля ничего не узнал. Его информация исчерпывается Гришиной суммой g и Колиной картой к (а Лешину сумму теперь Коля и сам может вычислить). Рассмотрим любую другую карту, пусть ее номер х. Покажем, что она входит в какой-нибудь набор из трех карт с суммой g, не содержащий к. Для этого дополним х парой карт с суммой номеров g – х. Таких пар ровно три при любом значении g – х (доказательство см. ниже). Из них две, возможно, не подходят из-за того, что туда входит карта с номером s или к, но как минимум одна пара остается. С ее помощью мы и создадим набор для Гриши (а набор для Леши получится автоматически). Например, если х = 3, то в нашем случае при g = 4 надо найти пару с суммой 4–3 = 1. Таких пар три: 1 = 0 + 1 = 2 + 6 = 3 + 5 (mod 7). Из них подходит только (0, 1}, то есть у Гриши мог быть набор 0, 1, 3.
Итак, любая карта могла оказаться у Гриши. Такие же рассуждения показывают, что любая карта могла оказаться и у Леши. Поэтому местоположение никакой из карт Коля вычислить не может.
Осталось доказать, что неупорядоченных пар с нужной суммой s всегда три. Есть семь упорядоченных пар (0, s), (1, s — 1)…, (6, s — 6). Из них ровно в одной оба остатка одинаковы, поскольку уравнение 2х = s имеет, ввиду взаимной простоты чисел 2 и 7, ровно одно решение. Из неупорядоченной пары с разными остатками получается ровно две упорядоченных, поэтому неупорядоченных пар вдвое меньше, чем упорядоченных, то есть ровно 3.
Ответ. Могут в обоих случаях.
Д45. Из Петиных слов следует, что он не комиссар. Возможны два случая:
1) Петя – мафиози. Тогда он лжет и на самом деле знает, кто Дима, поэтому Дима – второй мафиози.
2) Петя – мирный житель.
Информации, которую Дима мог бы извлечь из Петиного высказывания, недостаточно, чтобы догадаться, кто комиссар. Поэтому если Дима говорит правду, то он сам и есть комиссар. А если лжет, то он – мафиози.
Если бы Миша был мирным жителем, он к этому моменту еще не мог понять, кто Петя: мирный житель или мафиози. Если Петя и Дима – два мафиози, то Миша комиссар; если Петя – мирный житель, а Дима – комиссар, то Миша – мафиози; если Петя – мирный житель, а Дима – мафиози, то Миша – комиссар или мафиози.
Теперь видно, что Саша, будучи мирным жителем, не может быть уверен, что Миша – комиссар. А комиссар никого другого назвать комиссаром не может. Значит, Саша – мафиози.
Теперь ясно почти все: Петя – мирный житель, Саша– первый мафиози, Дима и Миша – комиссар и второй мафиози (в произвольном порядке), а Илья – мирный житель.
Ответ. Мирный житель.
Д46. Обсуждение. Пусть дочь полковника звали Кити, а гусаров – Алексей, Борис и Виктор. О чем имеет смысл спрашивать гусаров? Либо сразу о том, кто кому бросал цветок, либо для начала о том, в каком порядке они ехали (ведь последний знает про всех, кроме себя). Оба пути приводят к верному решению. Только надо понимать, что на прямой вопрос «Кто ехал последним?» гусар не может ответить (все три ответа «Так точно», «Никак нет» и «Не могу знать» не подходят).
Решение 1. Сначала спросим Алексея: «Ехал ли Борис впереди Виктора?» Ответ однозначно определяет, кто передний: «Так точно» – Борис, «Никак нет» – Виктор, «Не могу знать» – Алексей.
Рассмотрим случай, когда информации минимум – то есть передний Алексей. Спросим у Бориса, бросила ли Кити цветок Виктору. При ответе «Так точно» цветок от Кити у Виктора. При ответе «Никак нет» полковник спрашивает Бориса, бросила ли Кити цветок Алексею. При ответе «Так точно» цветок от Кити у Алексея, при ответе «Никак нет» – у Бориса.
Если же на второй вопрос Борис ответил «Не могу знать», то Виктор ехал позади Бориса и Алексей получил цветок не от Кити. Тогда спросим у Виктора, бросала ли Кити цветок Борису. При ответе «Так точно» цветок от Кити у Бориса, «Никак нет» – у Виктора.
Решение 2. Сначала полковник спрашивает у Алексея, бросила ли Кити цветок Борису. При ответе «Так точно» всё ясно. При ответе «Никак нет» Борис вне подозрений, и полковник спрашивает у Алексея, бросила ли Кити цветок
Виктору. При ответах «Так точно» и «Никак нет» на этот вопрос всё ясно (в первом сучае цветок брошен Виктору, во втором – Алексею), а ответ «Не могу знать» означает, что Виктор ехал последним. Осталось спросить Виктора, бросила ли Кити цветок Алексею.
Ответ «Не могу знать» на первый вопрос означает, что Борис ехал позади Алексея. Тогда полковник спрашивает Бориса, бросила ли Кити цветок Виктору. При ответе Бориса «Так точно» всё ясно. При ответе «Никак нет» Виктор вне подозрений, а Борис ехал последним. Осталось спросить Бориса, бросила ли Кити цветок Алексею.
Ответ Бориса «Не могу знать» означает, что Виктор ехал последним. Вне подозрений Алексей (если бы цветок достался ему, Борис ответил бы «Никак нет»). Осталось спросить Виктора, бросила ли Кити цветок Борису.
Д47. Решение. Попробуем задавать те же вопросы, что и во втором решении задачи про трех гусаров. Спросим у Алексея, бросила ли Кити цветок Борису. Если Алексей ответит «Так точно», все ясно. Если Алексей ответит «Никак нет», можно вычеркнуть Бориса из списка. Разбираться с оставшимися тремя гусарами с помощью трех оставшихся вопросов мы уже умеем.
Если же Алексей скажет «Не могу знать», спросим Бориса, бросила ли Кити цветок Виктору. При ответе Бориса «Так точно» все ясно. При ответе Бориса «Никак нет» вычеркиваем Виктора из списка. Остались три гусара и, казалось бы, всего два вопроса. Но вспомним, что Алексей уже ответил «Не могу знать» на вопрос, бросила ли Кити цветок Борису. А вместе с этим вопросом получается три вопроса, и задача вновь сводится к уже решенной задаче о трех гусарах.
Кого же вычеркивать из списка, если Борис, как и Алексей, ответит «Не могу знать»? Алексея! Ибо он ехал впереди Бориса (раз не знает, бросила ли Кити цветок
Борису). Поэтому если бы Кити бросила цветок Алексею, Борис бы это видел и знал бы, что цветок брошен не Виктору. На трех гусаров остались снова два вопроса, но третьим можно считать вопрос «Бросила ли Кити цветок Виктору?», на который Борис уже ответил «Не могу знать».
Итак, в любом случае задача про четырех гусаров сводится к уже решенной задаче о трех гусарах.
Заметим, что в своих рассуждениях мы нигде не использовали, что гусаров именно четверо. Вместо этого показано, что если разрешено задавать больше на один вопрос, то на один увеличивается и число гусаров, с которыми сможет разобраться полковник. Поэтому ему хватит десяти вопросов, чтобы выяснить, кому из десяти гусаров бросила цветок его дочь.
Комментарий. Строго излагать это решение удобно с помощью метода математической индукции. При этом в качестве базы индукции достаточно решить задачу о двух гусарах и двух вопросах.
Д48. Если бы на голове первого мудреца был белый колпак, то второй бы догадался, что на его голове черный колпак. Поэтому на голове первого черный колпак.
Д49. Третий мудрец видит два черных колпака и не знает, черный на нем колпак или белый. Поэтому он ответит «Не знаю». Если бы на втором мудреце был белый колпак, то третий все равно не смог бы определить цвет своего колпака. Поэтому второй мудрец тоже ответит «Не знаю». А третий подумает так: «Если на мне и на втором белые колпаки, то третий бы определил цвет своего колпака. Второй это понимает не хуже меня. Поэтому если на мне белый, а на втором черный, то по ответу третьего «Не знаю» второй бы определил цвет своего колпака. А раз они оба сказали «Не знаю», на мне черный колпак. Итак, первый скажет: «На мне черный колпак».
Ответ. Третий и второй скажут «Не знаю». Первый скажет «На мне черный колпак».
Комментарий. Условие этой задачи слегка отличается от условия задачи 10.4: не все мудрецы видят друг друга. Но это не влияет ни на решение, ни на ответ.
Д50. 1) Так как мудрецов десять, а колпаков каждого цвета по три, колпаки всех четырех цветов на кого-то надеты. Поэтому если последний мудрец не видит перед собой никого в желтом колпаке, он ответит: «На мне желтый». А если он этого не скажет, то все поймут, что он видел перед собой кого-то в желтом колпаке. Если предпоследний мудрец не увидит никого перед собой в желтом колпаке, то он догадается, что желтый колпак на нем. А если он не скажет «На мне желтый колпак», все поймут, что он тоже видел перед собой кого-то в желтом колпаке. Первый из мудрецов, перед которым нет никого в желтом колпаке (и который не слышал ни от кого слов «На мне желтый колпак»), поймет, что желтый колпак как раз на нем.
2) Как показано в предыдущем пункте, как минимум один мудрец определит, что на нем желтый колпак, как минимум один – что на нем красный колпак, как минимум один – синий и как минимум один – зеленый.
Замечание. При «удачных» расстановках смогут назвать цвет своего колпака более четырех мудрецов. В частности, если два колпака какого-то цвета спрятаны, а третий надет на самого последнего мудреца, то он сможет определить цвет своего колпака. Отсюда остальные мудрецы догадаются, что этого цвета больше ни на ком нет, поэтому определить цвет своего колпака сможет каждый.
Д51. Подсказка. Рассмотрите сначала случаи попроще: белых колпаков не принесли совсем, принесли только один, только два и т. д.
Решение. Вместо одной задачи решим целую цепочку задач, начиная с совсем простых:
Задача 0. Если бы белых колпаков не было, то каждый мудрец смог бы определить, что на нем черный колпак.
Задача 1. Если белый колпак один, то первый мудрец ответить бы не смог, а остальные сказали бы, что на них черные колпаки, подумав так: если бы на мне был белый колпак, то первый бы его видел и смог бы понять, что на нем черный колпак (так как он умеет решать задачу 0), но он промолчал.
Задача 2. Если белых колпаков два, то первый мудрец, конечно же, промолчал бы. Второй бы подумал: независимо от цвета моего колпака остались еще и черные, и белые, поэтому первый мудрец в любом случае промолчал бы, и я тоже ничего не могу определить. Третий бы подумал: если бы на мне был белый колпак, то второй бы понимал, что белый остался только один и определил бы цвет своего колпака (так как задачу 1 он решать умеет), поэтому на мне черный колпак. Так же подумали бы и остальные и назвали бы цвета своих колпаков.
Задача 3. Если белых колпаков три, то цвет своего колпака смог бы определить четвертый мудрец (и все последующие). Ведь если бы на нем был белый колпак, то третьему мудрецу пришлось бы решать задачу 2, а это он делать умеет. Раз третий промолчал, четвертому все ясно.
Рассуждая аналогично, приходим к выводу, что определить цвет своего колпака смогут все мудрецы, начиная с одиннадцатого.
Более строго решение может быть изложено с помощью метода математической индукции.
Д52. Решим для начала более простую задачу. Пусть есть только 3 красных и 2 синих колпака, мудрецов всего трое, и султан надел на головы первому и второму мудрецам красные колпаки, а третьему – синий. Через одну минуту никто не выйдет, после чего первый мудрец подумает: «Если на мне синий колпак, то второй видит два синих колпака и понимает, что на нем красный. Почему же он не вышел? Потому что на мне красный колпак!» Аналогично сможет на второй минуте определить цвет своего колпака и второй мудрец. Третий мудрец ничего понять пока не сможет: если на нем был бы красный колпак, то каждый из двух остальных на первом шаге видел два красных колпака и все равно не мог бы ничего определить. Но за третью минуту он поймет: раз другие мудрецы раньше меня догадались о цвете своих колпаков, они видели не то же самое, что и я. Я видел два красных колпака, а они – красный и синий. Итак, на мне синий колпак».
Вернемся к нашей задаче. Перенумеруем мудрецов: у первого, второго и третьего белые колпаки, у четвертого и пятого красные и у шестого – синий. Если бы на первом был синий колпак, то через одну минуту все бы оставались на местах, а на второй минуте второй мудрец подумал бы: «Я вижу оба синих колпака. Если на мне красный, то третий мудрец видит все красные и все синие колпаки и должен был сразу понять, что на нем белый (здесь тонкость, разберемся позже). Почему же он не вышел? Потому что на мне белый колпак!»
Если бы на первом был красный колпак, второй мудрец рассуждал бы аналогично: «Я вижу все три красных колпака. Если на мне синий, то третий мудрец видит все красные и все синие колпаки и должен был сразу понять, что на нем белый. Почему же он не вышел? Потому что на мне белый колпак!»
Но на первом не синий и не красный колпак. Поэтому через две минуты второй мудрец останется на месте (аналогичная тонкость, ее тоже отложим на потом). Первый мудрец рассуждает не хуже нас с вами и из того, что второй никуда не ушел через две минуты, поймет к концу третьей минуты, что ему надо выйти в белую дверь. Вместе с ним выйдут находящиеся в таком же положении второй и третий мудрецы.
После этого каждый из трех оставшихся мудрецов подумает: «Если бы на мне был белый колпак, то я был бы точно в том же положении, что и первые трое. Но они уже определили цвет своего колпака, а я еще нет. Почему же? Потому что я не в белом колпаке!» И тут же продолжит: «Два других мудреца, пока не угадавших цвет своих колпаков, тоже только что поняли про себя, что колпаки на них не белые. Мы все теперь можем исключить из рассмотрения четыре белых колпака и ушедших мудрецов. Задача сведена к предыдущей». Как уже показано, после этого мудрецы в красных колпаках потратят еще две минуты на определение цвета своих колпаков, а за третью минуту разберется и мудрец в синем колпаке.
Вот теперь обсудим тонкие места. Мы воспользовались тем, что на второй минуте третий и второй мудрецы еще не могли определить цвет своего колпака. А вдруг могли, просто мы не настолько мудры, чтобы понять, как именно? К счастью, даже если бы и могли, на ответ это бы не повлияло. Ведь это значило бы просто, что все мудрецы в белых колпаках определили их цвет на минуту раньше, чем мы думаем. Ну и прекрасно: определили же! Заметим также, что если мудрецы в красных и синем колпаках тоже могли бы как-то определить цвета своих колпаков раньше, чем описано в нашем решении, это по аналогичной причине не повлияло бы на ответ: «белые» мудрецы в своих размышлениях не используют сидение на месте «красных» и «синего», а «красные» – сидение «синего».
Д53. Если у одного из мудрецов нечетное число, то он сразу скажет: «Я знаю твое число». Поэтому первое утверждение «Я не знаю твоего числа» следует понимать как «Мое число четное».
Если число второго мудреца не кратно четырем, то он из этого сделает вывод, что у первого мудреца число вдвое больше, и определит его. Иначе он тоже скажет: «Я не знаю твоего числа», что будет означать «Мое число кратно четырем».
Если число первого мудреца не кратно 8, то он сможет определить число партнера, умножив на 2 свое число. Иначе он тоже скажет: «Я не знаю твоего числа», что будет означать «Мое число кратно восьми» и т. д.
Поскольку числа, данные мудрецам, не могут делиться на сколь угодно большую степень двойки, рано или поздно этот процесс прекратится.
Д54. Подсказка. Чтобы лучше разобраться в этой довольно сложной задаче, решим для начала аналогичную для трех мудрецов и чисел от 1 до 10. Пусть палач обошел всех по три раза, а в начале четвертого обхода первый мудрец сказал, что наибольшее число у него.
Запишем по порядку утверждения про числа, соответствующие высказываниям мудрецов.
1 мудрец: «У меня не 10».
2 мудрец: «У меня не 10».
3 мудрец: «У меня не 10 и не 9».
1 мудрец: «У меня не 9».
2 мудрец: «У меня не 9 и не 8».
3 мудрец: «У меня не 8».
1 мудрец: «У меня не 8 и не 7».
2 мудрец: «У меня не 7».
3 мудрец: «У меня не 7 и не 6».
1 мудрец: «У меня 6, и это самое большое число».
Решение. До того, как первый мудрец сказал, что его число максимальное, мудрецы успели сделать 1000 высказываний. В первых 9 утверждалось только, что у соответствующего мудреца не 1000, в следующих 9 – что не 999 (при этом в первом из этих следующих дополнительно утверждалось, что и не 1000), в следующих 9 – что не 998 (при этом в первом из этих следующих дополнительно утверждалось, что и не 999). Разделим 1000 на 9, получим в частном 111 и в остатке 1. Это означает, что в 999-м высказывании девятый мудрец утверждал, что у него не 890, в 1000-м десятый мудрец сообщил, что у него не 890 и не 889. До этого остальные уже успели сказать, что у них не 890. Поскольку этого как раз хватило первому мудрецу, чтобы понять, что его число – максимальное, этим числом было 889.
Ответ. 889.
Д55. Какие выводы можно сделать из первой фразы А? Во-первых, известное ему произведение P не является произведением двух простых чисел p1 и p2 (иначе разложение 1 · p1 · p2 было бы единственным). Во-вторых, если произведение трех различных натуральных чисел не превосходит 50, то их сумма не превосходит 1 + 2 + 25 = 28. А раз число, которое сообщили математику А, могло бы быть и суммой трех чисел, оно не больше 28. С другой стороны, Р не меньше 21. Действительно, если бы Р было меньше 21, то были бы возможны как минимум два варианта троек чисел с суммой Р: 1 + 2 + (Р – 3) (произведение не больше 1. 2.17 = 34) и 1 Н- 3 (Р – 4) (произведение не больше 1-3-16 = 48).
Есть только два числа, соответствующие первой фразе А: 24 и 28.
24 = 1– 2-12 = 1– 3–8 = 1– 4–6 = 2– 3–4 (суммы соответственно 15, 12, 11 и 9);
28 = 1– 2-14 = 1– 4–7 (суммы соответственно 17 и 12).
Ответ Б «Я все равно не знаю их» означает, что известная ему сумма встречается среди этих вариантов более одного раза, т. е. равна 12. Если А сообщили число 24, то он сделает вывод, что задуманы числа 1, 3 и 8. А если ему сообщили число 28, то он поймет, что задуманы числа 1, 4 и 7.
Д56. Зная номера троих других а < b < с, математик понимает, что его номер равен либо а + b + с, либо с – а – b. Раз математик не смог определить свой номер, оба этих выражения должны давать двузначное число (то есть лежать в пределах от 10 до 99) и не совпадать с другими номерами.
Пусть 10 ≤ x < y < z < t ≤ 99—искомые номера, тогда t = x + y + z. Поскольку математик с номером t знает числа x < y < z, число z − x − y двузначно и отлично от x и y. Но тогда z = x + y + (z − x − y) ≥ 10 + 11 + 12 = 33. Заметим еще, что t = z + y + x ≥ z + 11 + 10, то есть t ≥ z + 21. Математик с номером x знает числа y < z < t, значит, y + z + t ≤ 99. Сложив это неравенство с неравенствами 11 ≤ y и z + 21 ≤ t, получим 2z ≤ 67, откуда z ≤ 33. Значит, z = 33. Далее, t = x + y + z > 10 + y + 33 = 43 + y, поэтому 99 > y + z + t > y + 33 + (43 + y) = 76 + 2y. Отсюда 2y ≤ 23, то есть y ≤ 11. Значит, y = 11, x = 10, z = 33 и t = 10 + 11 + 23 = 54. Нетрудно убедиться, что этот набор удовлетворяет условию.
Ответ. 10, 11, 33 и 54.
Д57. Пусть x, y, z – числа, написанные на лбу первого, второго и третьего логика соответственно.
Вначале с точки зрения первого логика возможны варианты x = y + z и x = |y − z|. Поэтому первый логик сможет догадаться, какое у него число, только если y = z. Значит, после первого высказывания все знают, что y ≠ z.
Теперь с точки зрения второго логика возможны такие варианты: y = x + z и y = |x − z|, причем y ≠ z. Поэтому второй логик сможет догадаться, какое у него число, только если x = z или x = 2z. Значит, после второго высказывания все знают, что x ≠ z и x ≠ 2z.
Тогда с точки зрения третьего логика возможны такие варианты: z = x + y и z = |x − y|, причем z не равно ни одному из чисел y, x или x/2. Поэтому третий логик сможет догадаться, какое у него число, только если x
{y, 2y, y/2, 2y/3}. Значит, после третьего высказывания все знают, что x
{y, 2y, y/2, 2y/3}.
Теперь с точки зрения первого логика возможны варианты x = y + z и x = |y − z|. При этом известно, что x /2 {y, 2y, y/2, 2y/3, z, 2z} и y ≠ z. Поэтому первый логик сможет догадаться, какое у него число, только если y + z или |y − z| равно одному из чисел y, 2y, y/2, 2y/3, z, 2z и y ≠ z. Это возможно, только если y − z равно одному из чисел y/2, 2y/3, z, 2z, −y, −2y, −y/2, −2y/3. В этих случаях x = y + z и равно 3y/2, 4y/3, 3z, 4z, 3y, 4y, 5y/2, 8y/3 соответственно. Поскольку 50 не делится ни на 3, ни на 4, то имеет место случай x = 5y/2. Тогда y = 20, z = 30.
Ответ. У второго 20, у третьего 30.