Ответ. Нельзя.
Д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.
