Задача 9.10. Есть 9 карточек с цифрами 1, 2, . . . , 9. Их перетасовали, отдали четыре Ивану, четыре Василисе и одну Бабе-Яге. Иван сообщил вслух, что сумма цифр на его карточках оканчивается на 7. 1) Знает ли теперь Василиса карточку Бабы-Яги? 2) Знает ли теперь Баба-Яга набор карточек Василисы? 3) Может ли случится, что про какую-то карточку, кроме своей, Баба-Яга знает, у кого она находится? Задача 9.11. Пять мудрецов играют в мафию. Среди них два мафиози, два мирных жителя и комиссар. Мафиози знают друг друга, комиссар знает все, мирные жители изначально ничего не знают. Мафиози могут говорить что угодно. Остальные говорят только то, в чем сами уверены. Состоялся разговор: А: «Д — мирный житель». Б: «Нет, Д — мафиози». В: «Д не знает, кто я». Г: «Д знает, кто я». Д: «Б — мафиози». Определите роли тех игроков, для кого это возможно. Задача 10.6. Как можно изменить количество колпаков в задаче о трех мудрецах, чтобы решение всех пунктов в точности сохранилось? Задача 10.7Ï Придумайте задачу, аналогичную задаче о трех мудрецах, для большего количества мудрецов. Решите задачу для четырех и для пяти мудрецов. Задача 10.8t В купе поезда собрались 7 мудрецов. Окно было открыто. Поезд въехал в тоннель, и лица всех мудрецов оказались испачканы сажей. Каждый видел, что и другие испачканы, но себя не видел и спокойно продолжал беседу. В купе вошел проводник и сказал: «Господа, среди вас есть люди с грязными лицами. В поезде воды нет. Зато на каждой станции поезд стоит достаточно долго, так что рекомендую испачкавшимся пойти и умыться». Несколько станций никто из мудрецов не реагировал на это замечание, но на некоторой станции все одновременно встали и пошли умываться. 1) На какой по счету станции мудрецы поняли, что следует умыться? 2) Парадокс проводника. Если бы проводник промолчал, каждый бы по-прежнему считал себя чистым и умываться не пошел бы. Но ведь каждый видел, что среди них есть испачкавшиеся, так что проводник, казалось бы, ничего нового не сказал. Так что же сказал проводник? Задача 10.9. Установим соответствие между задачами о колпаках и о проводнике (при одинаковом количестве мудрецов). Будем считать, что на мудреце с грязным лицом надет черный колпак, а иначе — белый. Тогда ответу «Не знаю» в задаче о колпаках соответствует нежелание умываться в задаче о проводнике. Как перевести слова проводника на язык задачи о колпаках? Задача 10.10. Три дамы сидят в купе с испачканными лицами и смеются. Вдруг А думает: «Почему Б не понимает, что В смеется над ней? О Боже! Они смеются надо мной!» Что в этой задаче играет роль проводника? Задача 10.11. Фразы типа «Это верно», «А знает, что это верно», «Б знает, что А знает, что это верно», «В знает, что Б знает, что А знает, что это верно» можно продолжать до бесконечности, и все они имеют разный смысл, но разницу эту с каждым «витком» улавливать все труднее. Придумайте подобные цепочки, где эта разница заметна. «Все» и «некоторые» Задача Д1. На крыльце дома сидят рядом мальчик и девочка. Саша говорит: «Я мальчик». Женя говорит: «Я девочка». Хотя бы один из них врет. Кто мальчик, а кто девочка? Задача Д2. В некоем конгрессе заседают 100 политических деятелей. Каждый из них либо продажен, либо честен. Известно, что: 1) по крайней мере один из конгрессменов честен; 2) из каждой произвольно выбранной пары конгрессменов по крайней мере один продажен. Сколько честных политических деятелей в этом конгрессе? Задача ДЗ. Из трех мальчиков, которых зовут Антон, Ваня и Саша, только один всегда говорит правду. Антон сказал: «Ваня не всегда говорит правду», Ваня сказал: «Я не всегда говорю правду», а Саша сказал: «Антон не всегда говорит правду». Кто же из них всегда говорит правду, если известно, что по крайней мере один из них солгал? Задача Д4. Истинно или ложно высказывание «Нет правил без исключения»? (Данное высказывание тоже является правилом.) Задача Д5. Сформулируйте отрицание к утверждению: «Каждый охотник желает знать, где сидит фазан». Предложите несколько вариантов. Задача Д6. Встретились несколько жителей острова рыцарей и лжецов, и каждый заявил всем остальным: «Вы все — лжецы». Сколько рыцарей было среди них? 107 Задача Д7. Какие из четырех утверждений верны, а какие нет? Почему? 1) Все прямоугольники — квадраты. 2) Все квадраты — прямоугольники. 3) Некоторые прямоугольники — квадраты. 4) Некоторые квадраты — прямоугольники. Задача Д8. 1) Неверно, что все друзья моего друга — мои друзья. Что тогда верно? 2) Неверно, что все ананасы неприятны на вкус. Что тогда верно? 3) Неверно, что некоторые волки — оборотни. Что тогда верно? Задача Д9. Во всех зоопарках, где есть гиппопотамы и носороги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов, есть гиппопотамы. Наконец, во всех зоопарках, где есть гиппопотамы и жирафы, есть и носороги. Может ли существовать такой зоопарк, в котором есть гиппопотамы, но нет ни жирафов, ни носорогов? Союзы «и», «или» Задача Д10. Аня просит купить яблоки и сливы, Боря — яблоки или абрикосы, Витя — абрикосы или персики, Галя — яблоки и персики. Денег у мамы хватает только на 3 вида фруктов. Как ей выполнить пожелания всех детей? Задача Д11. Замените высказывания барона Мюнхгаузена на противоположные: 1) Луна сделана из сыра, а Солнце из масла. 2) Я видел медведя, а он меня — нет. 3) Я не боюсь ни львов, ни крокодилов. 4) Лошадь заблудилась или ее засыпало снегом. 5) Я отправился в разведку на коне или на ядре. Задача Д12. Первого апреля кто-то поменял таблички на дверях в учительскую, столовую и спортзал. Ни одна из трех новых табличек: «Столовая», «Спортзал», «Сто- 108 ловая или спортзал» не соответствует действительности. Куда ведет дверь с табличкой «Спортзал»? Задача Д13. Судья допрашивает трех свидетелей. Жан утверждает, что Жа к лжет, Жа к обвиняет во лжи Руссо, а Руссо уговаривает не верить ни Жану, ни Жаку. Кто из свидетелей говорит правду? Задача Д14. Перед нами два жителя острова рыцарей и лжецов, А и Б. А говорит: «Я лжец, а Б рыцарь». Кто А и кто Б? Задача Д15. Как-то встретились три жителя острова рыцарей и лжецов: Ах, Ох и Ух. Один из них сказал: «Ах и Ох — оба лжецы», другой сказал: «Ах и Ух — оба лжецы» (но кто именно что сказал — неизвестно). Сколько всего лжецов среди этих трех аборигенов? Задача Д16. Житель острова рыцарей и лжецов А в присутствии другого жителя этого острова Б сказал: «По крайней мере один из нас лжец». Кто такой А и кто такой Б? Задача Д17. На острове живут рыцари, лжецы и хитрецы, которые могут как говорить правду, так и лгать. Путешественник встретил двух островитян. На вопрос «Вы оба лжецы?» каждый ответил «Да». Что можно узнать по этому ответу? Задача Д18. Среди трех человек, А, Б и В, есть рыцарь, лжец и хитрец. Они сказали: А: «Я хитрец». Б: «И А, и В иногда говорят правду». В: «Б хитрец». Кто из них рыцарь, кто лжец, а кто хитрец? Задача Д19. Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы: Володя: «Это сделал Саша». Аня: «Володя лжет!» Егор: «Маша разбила». 109 Саша: «Аня говорит неправду!» Рома: «Разбила либо Маша, либо Нина». Маша: «Это я разбила!» Нина: «Маша не разбивала!» Коля: «Ни Маша, ни Нина этого не делали». Олег: «Нина не разбивала!» Кто разбил окно, если известно, что из этих девяти высказываний истинны только три? Задача Д20. Незнайка лжет по понедельникам, вторникам и пятницам, а в остальные дни недели говорит правду. В какие дни недели Незнайка может сказать: «Я лгал позавчера и буду лгать послезавтра»? Задача Д21. На заседании Государственной думы на острове рыцарей и лжецов часть депутатов утверждала, что и во фракции рыцарей, и во фракции лжецов четное число депутатов. Остальные же доказывали, что и в той, и в другой фракции нечетное число депутатов. Подводя итоги, спикер заметил, что всего в думе 213 депутатов. Кто он — рыцарь или лжец? Следствие Задача Д22. Если волк встретит зайца, то сразу съест его. Волк, съевший зайца, радуется. По лесу идет радостный волк. Означает ли это, что он встретил зайца? Задача Д23. Известно, что: • Если Иван — брат или сын Марьи, то Иван и Марья — родственники. • Иван и Марья — родственники. • Иван — не сын Марьи. Можно ли вывести следствие, что Иван — брат Марьи? Задача Д24. Житель острова рыцарей и лжецов сказал, показав на другого жителя: «Если я рыцарь, то он — лжец». Можете ли вы определить, кто есть кто? Задача Д25. У одного из трех друзей: Львова, Волкова и Щукина — дома живет кошка, у другого собака, а третий разводит рыбок. Если у Щукина собака, то у Волко- 110 ва кошка. Если у Щукина кошка, то у Волкова аквариум. Если у Волкова нет собаки, то и у Львова нет собаки. Если у Львова рыбки, то у Щукина — кошка. Кто у кого живет? Задача Д26. Серый волк позвонил на Бейкер-стрит и заявил, что у него украли очень ценную вставную челюсть, инкрустированную бриллиантами. Подозреваемые — Ниф-Ниф, Нуф-Нуф и Наф-Наф. Известно, что: 1) каждый из троих подозреваемых в день кражи был у волка и никто другой в краже не участвовал; 2) если Ниф-Ниф виновен, то у него был ровно один сообщник; 3) если Нуф-Нуф невиновен, то невиновен также и Наф-Наф; 4) если Наф-Наф невиновен, то невиновен также и Нуф-Нуф; 5) если виновны двое, то Ниф-Ниф — один из них. Кому Шерлок Холмс предъявит обвинение? Задача Д27. У Кролика украли бочонок меда. Кролик подозревает в краже ослика Иа-Иа, Винни-Пуха, Тигру и Пятачка. Неопровержимыми уликами доказано, что: 1) кто-то из них обязательно виновен; 2) никто больше не мог польститься на мед; 3) Пятачок всегда действует только вместе с Винни; 4) если Иа-Иа виновен, то у него было ровно два соучастника; 5) если виновен Тигра, то у него был ровно один соучастник. Чья вина не вызывает сомнения? Задача Д28. В строку записано 9 чисел. 1) Верно ли, что если сумма любых четырех соседних чисел положительна, то и сумма всех девяти чисел положительна? 2) Верно ли, что если сумма любых четырех из них положительна, то и сумма всех девяти чисел положительна? 111 Выводы Задача Д29. Определите, какие из приведенных рассуждений истинны, а какие ложны. 1) Некоторые улитки являются горами. Все горы любят кошек. Значит, все улитки любят кошек. 2) Две поляны никогда не похожи одна на другую. Сосны и ели выглядят совершенно одинаково. Значит, сосны и ели не являются двумя полянами. Задача ДЗО. Сделайте вывод (наиболее полный), если это возможно. 1) Ни у одного ископаемого животного не может быть несчастной любви. У устрицы может быть несчастная любовь. 2) Это свыше моего терпения! Со мной никогда не случалось ничего, что было бы свыше моего терпения. 3) Ни один император не стоматолог. Всех стоматологов боятся дети. 4) Дети нелогичны. Тот, кто управляет крокодилами, достоин уважения. Нелогичные персоны не достойны уважения. 5) Мои кастрюли — это единственное, что сделано из олова. Я считаю, что все твои подарки довольно полезны. Мои кастрюли — самые бесполезные вещи в доме. Задача Д31. В магазине продаются два вида булочек: с изюмом и с джемом. Известно, что булочки с изюмом всегда мягкие; некоторые мягкие булочки привезены сегодня утром; все мягкие булочки вкусные. Следует ли из этого, что: 1) все мягкие булочки — это булочки с изюмом; 2) все булочки с изюмом вкусные; 3) все булочки с джемом жесткие; 4) некоторые вкусные булочки привезены сегодня утром; 5) некоторые булочки с изюмом привезены сегодня утром; 112 6) все вкусные булочки мягкие; 7) все жесткие булочки невкусные; 8) сегодня утром не привозили булочек с джемом? Задача Д32. Верно ли сделаны выводы? В чем разница между задачами? 1) Гоголь написал «Мертвые души». На стене висит портрет Гоголя. Вывод: на стене висит портрет автора «Мертвых душ». 2) Какой-то человек изобрел самовар. На стене висит портрет какого-то человека. Вывод: на стене висит портрет изобретателя самовара. Доказательство от противного Задача ДЗЗ. Существует ли наименьшее положительное рациональное число? Задача Д34. Каждый месяц Папа Карло зарабатывал разное число золотых и за год заработал всего 60 золотых. Докажите, что в какой-то из месяцев он заработал нецелое число золотых. Задача Д35. По кругу написаны все целые числа от 1 до 2010 в таком порядке, что при движении по часовой стрелке числа поочередно то возрастают, то убывают. Докажите, что какие-то два четных числа стоят рядом. Задача Д36? Можно ли бумажный круг разрезать на несколько частей по прямым линиям и дугам окружностей и составить из них квадрат той же площади? Задача Д37! Каждый из голосующих на выборах вносит в избирательный бюллетень фамилии 10 кандидатов. На избирательном участке находится 11 урн. После выборов выяснилось, что в каждой урне лежит хотя бы один бюллетень и при всяком выборе 11 бюллетеней по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата. 113 Равносильность Задача Д38. Каково наибольшее число утверждений из приводимых ниже, которые одновременно могут быть истинными? 1) Джо ловкач. 2) Джо не везет. 3) Джо везет, но он не ловкач. 4) Если Джо ловкач, то ему не везет. 5) Джо является ловкачом тогда и только тогда, когда ему везет. 6) Либо Джо ловкач, либо ему везет, но не то и другое одновременно. Метаголоволомки Задача Д39. Илье Муромцу, Добрыне Никитичу и Алеше Поповичу за верную службу дали 6 монет: 3 золотых и 3 серебряных. Каждому досталось по две монеты. Илья Муромец не знает, какие монеты достались Добрыне, а какие Алеше, но знает, какие монеты достались ему самому. Придумайте вопрос, на который Илья Муромец ответит «да», «нет» или «не знаю» и по ответу на который вы сможете понять, какие монеты ему достались. Задача Д40. Мудрец встретил трех человек. Он знал, что среди них есть рыцарь, хитрец и лжец. Мудрец спросил первого: «Вы кто?» Тот ответил. «По такому ответу я не могу узнать, кто он», — подумал мудрец. Тогда он спросил о том, кем является первый, остальных двух. Они ответили, и все три ответа оказались разными по смыслу. Тогда мудрец подумал и сказал: «Теперь понятно». Кто уке был этот первый? Задача Д41. Судье известно, что из двух подозреваемых А и Б один — рыцарь, а другой — шпион, который может как лгать, так и говорить правду. Судья спросил у А, шпион ли Б. После ответа А он сразу понял, кто шпион. Кто же? 114 Задача Д42! Перед судом предстали трое обвиняемых: А, Б и В. Суду было известно, что один из них рыцарь, другой лжец, а третий шпион (способный как говорить правду, так и лгать). Но кто есть кто, суд не знал. Подсудимого А судья спросил: — Вы шпион? А ответил односложно («да» или «нет»). Тогда судья спросил обвиняемого Б: — Сказал ли А правду? Ответил Б также односложно («да» или «нет»). В этот момент А заявил: — Обвиняемый В не шпион. Судья ответил: — Я и раньше знал это, а теперь я знаю, кто шпион. 1) Кто шпион? 2) Что сказал Б? Задача Д43? В некотором королевстве живут граждане трех типов: а) дурак считает всех дураками, а себя умным; б) скромный умный про всех знает правильно, а себя считает дураком; в) уверенный умный про всех знает правильно, а себя считает умным. В думе 200 депутатов. Премьер-министр провел анонимный опрос думцев: сколько умных в этом зале сейчас находится? По результатам опроса он не смог понять ответ. Но тут из поездки вернулся единственный депутат, не участвовавший в опросе. Он ответил на вопрос про всю думу, включая себя, и, увидев этот ответ, премьер-министр всё понял. Сколько умных в думе могло быть (включая путешественника)? Задача Д44! Из колоды вынули 7 карт, показали всем, перетасовали и раздали Грише и Леше по 3 карты, а оставшуюся карту 1) спрятали; 2) отдали Коле. Гриша и Леша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычис- 115 лить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Леша не договаривались о каком-либо особом способе общения; все переговоры происходят открытым текстом.) Задача Д45! Петя, Дима, Миша, Саша и Илья играют в мафию. Среди них два мафиози, два мирных жителя и комиссар. Мафиози знают только друг друга, комиссар знает роль каждого, мирные жители не знают роли других игроков. Мафиози всегда лгут. Комиссар и мирные жители говорят правду. Мальчики сделали следующие заявления (в указанном порядке): Петя: «Я не знаю, кто Дима». Дима: «Я знаю, кто комиссар». Миша: «Я знаю, кто Петя». Саша: «Я знаю, что Миша — комиссар». Кто Илья? Задача Д46! Трое гусаров ехали по улице друг за другом. Каждому в руки упало по цветку от девушек на балконе. Гусары знают, кто был в строю, но каждый видел только, кто и в каком порядке ехал впереди него и кто им бросал цветы (а кто бросил ему самому — не знает). Полковник видел только то, что его дочь бросила цветок ровно одному из этих гусаров, и гусары тоже это знают. Полковник знает, кто именно ехал, но в каком порядке — не знает. Он может вызывать гусаров поодиночке и задавать им вопросы, на которые те честно отвечают «Так точно», «Никак нет» или «Не могу знать». Как полковнику за три вопроса узнать, кому из них бросила цветок его дочь? Задача Д47! Хватит ли полковнику из предыдущей задачи четырех вопросов, чтобы узнать, кому из четырех гусаров бросила цветок его дочь? А десяти вопросов, если гусаров было десять? Мудрецы и колпаки Во всех задачах этого и следующего разделов считается, что мудрецы рассуждают быстро и безошибочно. Каж- 116 дому известно, что остальные участники — тоже мудрецы. Если мудрец может точно ответить на заданный вопрос, он всегда честно отвечает. Если не может, то не пытается угадать, а говорит «Не знаю». Мудрецы, стоящие в колонне (в затылок друг другу), видят колпаки всех стоящих впереди, но не видят ни своего колпака, ни колпаков стоящих сзади мудрецов. Все мудрецы слышат ответы других мудрецов. Задача Д48. Двум мудрецам принесли два черных и один белый колпак. Затем их поставили в затылок друг другу и надели на каждого по колпаку. После этого спросили сначала второго, а потом первого, знает ли он, какого цвета колпак на его голове. Второй мудрец сказал, что не знает. А первый правильно назвал цвет своего колпака. Какой именно? Задача Д49. Трем мудрецам принесли три черных и два белых колпака. Затем их построили в затылок друг другу, после чего надели на каждого по черному колпаку. После этого стали по очереди спрашивать каждого мудреца, начиная с последнего, какого цвета у него колпак. На это мудрецы либо отвечают «Не знаю», либо называют цвет. Что будут отвечать мудрецы? Задача Д50? Десяти мудрецам принесли по три желтых, синих, красных и зеленых колпака. Мудрецов построили в затылок друг другу и надели каждому по колпаку, а два оставшихся колпака спрятали. Затем по очереди, начиная с последнего, стали спрашивать каждого, какого цвета у него колпак. На это мудрецы либо отвечают «Не знаю», либо называют цвет. 1) Докажите, что кто-то из мудрецов назовет цвет. 2) Докажите, что назовут цвет не менее четырех мудрецов. Задача Д51? Двадцати мудрецам принесли 10 белых и 50 черных колпаков. Затем им завязали глаза и надели каждому на голову по черному колпаку, а все ненадетые колпаки спрятали. После этого им развязали глаза и стали 117 у каждого по очереди спрашивать, какого цвета колпак у него на голове. Какой по счету мудрец сможет назвать цвет? Что будут говорить следующие? Задача Д521с Султан пригласил шестерых мудрецов в комнату с тремя дверьми: белой, красной и синей — и достал 4 белых, 3 красных и 2 синих колпака. Мудрецы сели в круг и крепко зажмурились. После этого султан надел троим мудрецам белые колпаки, двоим красные и одному синий. Открыв глаза, мудрецы получили возможность видеть цвета колпаков у всех остальных, но не у себя. Каждую минуту раздается удар гонга, после которого все мудрецы, знающие цвет своего колпака, должны выйти в дверь соответствующего цвета. Сколько мудрецов смогут покинуть комнату? Мудрецы и числа Задача Д53. Каждому из двух мудрецов дали бумажку с написанным на ней натуральным числом и сообщили, что одно число вдвое больше другого. Когда мудрецы посмотрели на числа, между ними состоялся такой диалог: А: «Я не знаю твое число». Б: «И я не знаю твое число». А: «И я не знаю твое число». Докажите, что рано или поздно кто-то из мудрецов сможет сказать: «Теперь я знаю твое число». Задача Д54? Султан вызвал 10 умнейших своих мудрецов и огласил правила нового испытания. Каждому мудрецу сообщат число от 1 до 1000 включительно, одно из чисел строго больше остальных. Затем каждого мудреца по очереди будут спрашивать, не у него ли максимальное число. Он может ответить «Не знаю» либо «У меня». После ответа «Не знаю» испытание продолжается, вопрос задают следующему мудрецу. Если последний мудрец ответил «Не знаю», вопрос опять задают первому 118 мудрецу и так далее. После ответа «У меня» испытание заканчивается. Если мудрец ответил правильно, всех мудрецов отпускают, если неправильно — всех мудрецов казнят. Мудрецам запретили не только обмениваться какой-либо информацией во время испытания, но даже договариваться о чем-либо заранее. Испытание началось. Королевский палач сто раз обошел всех мудрецов, и сто раз каждый из них ответил «Не знаю». Наконец, палач в сто первый раз спросил первого мудреца, не у него ли максимальное число. «У меня!» —ответил мудрец. Конечно, ответ был правильный, всех мудрецов отпустили. Какое число было у первого мудреца? Задача Д55! Математик В предложил математикам А и Б такую загадку: — Я задумал три попарно различных натуральных числа, произведение которых не превосходит 50. Сейчас я конфиденциально сообщу А это произведение, а Б — сумму задуманных чисел. Попробуйте отгадать эти числа. Узнав произведение и сумму соответственно, А и Б вступили в диалог: А: «Я не знаю этих чисел, но если бы мое число было суммой, я бы их знал». Б: «Я все равно не знаю их». Докажите, что теперь А сможет определить числа. Задача Д56? В одиночных камерах сидят 4 друга-математика. Каждому из них сообщили, что их номера в списке различны, двузначны и один из этих номеров равен сумме трех других. Но, даже узнав номера троих других, никто из них не смог вычислить свой номер. Так какие же у них были номера? Задача Д57? Каждому из трех логиков написали на лбу натуральное число, причем одно из этих чисел являлось суммой двух других, и сообщили им об этом. Логик не видит, что написано у него на лбу, но видит, что написано 119 у других. Первый логик сказал, что не может догадаться, какое число написано у него на лбу. После этого то же самое сказал второй логик, а затем и третий. Тогда первый сказал: «Я знаю, что у меня на лбу написано число 50». Какие числа написаны у двух остальных?