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

Осталось доказать, что неупорядоченных пар с нужной суммой 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 он решать умеет), поэтому на мне черный колпак. Так же подумали бы и остальные и назвали бы цвета своих колпаков.