Задача 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.
