Сто шляп
Задача
К злобному тюремщику (см. задачу «Заключённые и переключатель») поступила новая партия заключённых. На сей раз их было не 10, а 100 человек. Чтобы не слишком долго терзать их пыткой ожидания, тюремщик предложил им новый эксперимент:
«Вы все будете расставлены по кругу, после чего я лично надену каждому из вас шляпу, на которой будет написано какое-то число от 1 до 100. Числа на шляпах могут повторяться. Каждый будет видеть числа на всех остальных заключённых, но не сможет увидеть число на собственной шляпе. После этого я дам каждому возможность назвать (не вслух, а только мне на ушко) ровно одно число. Если хотя бы один заключённый угадает число на своей шляпе — всех отпущу сразу, а если нет — отправлю вас всех на урановые рудники. А вот если замечу подсказки и перемигивания — велю всех немедленно казнить.»
Посовещавшись и выработав стратегию действий, заключённые согласились. Как они должны действовать, чтобы выйти на свободу?
Подсказка 1
Если бы заключённые могли называть что-то вслух, то задача была бы совсем простой: достаточно договориться, что самый первый из них назовёт число, написанное на шляпе своего соседа справа, — тогда этот сосед, когда до него дойдёт очередь, сможет дать правильный ответ. Однако злобный тюремщик, увы, перекрыл эту возможность.
Можно, конечно, попытаться угадать число, игнорируя числа на всех остальных заключённых. Увы, это не лучшая идея. Каждый при этом ошибётся с вероятностью 99/100. Какова при этом вероятность того, что никто не назовёт правильно свой номер, то есть ошибутся все? Она равна 0,99100. Это не очень много — чуть больше, чем 0,366, — то бишь шанс выйти на свободу при такой стратегии почти 2/3. Но почему бы не придумать что-нибудь получше?
Подсказка 2
Если бы числа были не от 1 до 100, а, например, от 1 до 2, то для успешной договорной стратегии хватило бы двоих заключённых, а остальные могли бы просто промолчать. Подумайте, как именно двое заключённых могли бы договориться в этом случае, чтобы гарантированно избежать отправки на рудники?
Подсказка 3
Пример договорённости на двоих (см. подсказку 2): Первый из них называет тюремщику тот же номер, который видит у другого, а второй называет НЕ тот номер, который видит. Если у них два разных номера, то правильно угадает второй, а если два одинаковых — первый. Таким образом, в каждом из возможных случаев ровно один заключённый даст правильный ответ. А большего, собственно, и не нужно.
А теперь пусть заключённых трое, и номера тоже от 1 до 3. Первый из них мог бы, например, поступать так: всегда называть тот номер, который он видит на втором.
Покажите, что двое остальных при этом не смогут добиться желаемого, то есть обеспечить себе выход на свободу в 100% случаев. А значит, стратегия первого должна быть какой-то иной. Подумайте, какой...
Решение
Как обычно пишутся «для публикации» решения не самых простых математических (да и не только математических) задач? Разумеется, сначала задачу нужно решить. Иногда на поиск решения у математиков уходят многие месяцы и даже годы. Можно привести такую аналогию: у ребенка есть куча деталек от конструктора типа «Лего», из которых ему хочется собрать что-то сложное (и изначально не предусмотренное). Скажем, велосипед. Он его собирает кое-как, но при этом понимает, какие именно детали ему нужны, а от каких можно избавиться. Потом разбирает и собирает заново, уже только из нужных деталей, вставляя каждую строго в нужном порядке и на нужное место. Получается замечательный велосипед, но без детальной «инструкции по сборке» никто другой повторить это не в состоянии.
В арсенале фокусников испокон веков есть аналогичный приём — «фокус со шляпой»: из шляпы, которая всем присутствующим кажется пустой, неожиданно появляется то кролик, то большая коллекция платков, то еще что-нибудь. Как всё это туда попало — зритель догадаться не в состоянии.
А ведь одна из высших ценностей любого рассуждения — это ход рассуждения.
Поэтому я попробую отойти от канона и описать тот долгий путь проб (и ошибок!), по которому я сам приходил к верному решению поставленной задачи. Как справедливо заметил один не слишком цитируемый ныне автор, «в науке нет широкой столбовой дороги, и только тот может достигнуть ее сияющих вершин, кто, не страшась усталости, карабкается по ее каменистым тропам.» Впрочем, в отношении математической науки то же самое утверждал еще Евклид: «в геометрии нет особых путей даже для царей»...
Так что за неимением царского пути начнем карабкаться по имеющемуся.
Напомним вопрос, поставленный в третьей подсказке: Может ли первый заключенный поступать так: всегда называть то число, которое он видит на втором? (Если да, то что при этом должны называть остальные заключённые. Если нет — то почему?)
Запишем возможные тройки чисел в том порядке, в котором стоят заключённые (от первого к третьему), предположив, что у первого заключённого написано число 1.
| Номер ситуации |
Числа на шляпах |
| 1) | 111 |
| 2) | 112 |
| 3) | 113 |
| 4) | 121 |
| 5) | 122 |
| 6) | 123 |
| 7) | 131 |
| 8) | 132 |
| 9) | 133 |
Пусть первый называет то, что видит на втором. То есть 1 в случаях 1)–3), 2 в случаях 4)–6) и 3 в случаях 7)–9). В ситуациях 1)–3) первый правильно угадал (хотя не знает об этом, так как не видит своего числа). Зато в остальных случаях он ошибся, поэтому хочется сделать так, чтобы угадал кто-то из остальных.
Например, с точки зрения второго заключённого ситуация 1) ничем не отличается от ситуаций 4) и 7): во всех этих ситуациях он видит на чужих шляпах две единички, а что написано на его шляпе, ему не известно. Аналогично, ситуация 2) с его точки зрения неотличима от 5) и 8), а ситуация 3) — от 6) и 9). Что это означает для него? А вот что: видя на шляпе первого единичку, он точно не должен называть число 1, но может попробовать называть какое-то другое число. Это позволит ему угадать в каких-то трех из остальных ситуаций 4)–9). Но тогда третьему «достанутся» для правильных ответов три оставшихся ситуации. А сможет ли он дать в них всех правильные ответы? Увы, нет, потому что с его точки зрения как минимум две из этих трех ситуаций неразличимы — он же не знает своего числа! Действительно, с точки зрения третьего все ситуации 4)–6) — это те, в которых он видит 1 на первом и 2 на втором, а значит, должен выбрать какое-то одно число в качестве своего ответа тюремщику. Выбрал. Один раз угадал и дважды промахнулся. В ситуациях 7)–9), аналогично, что-то выбрал, в результате в одной из ситуаций угадал, а в двух других ошибся. Итого получил только два выигрыша, а не три, как хотелось.
Отсюда делаем такой вывод: мы не должны оставлять третьему заключённому такие ситуации, которые для него неразличимы. Иначе говоря, он должен выигрывать в одной из ситуаций 1)–3), в одной из ситуаций 4)–6) и в одной из ситуаций 7)–9). Из соображений симметрии следует, что и остальные двое тоже должны выигрывать по разу в каждой из троек ситуаций, которые для них неразличимы. То есть второй должен выигрывать один раз из 1) + 4) + 7), один раз из 2) + 5) + 8) и один раз из 3) + 6) + 9). Что касается первого, то для него все ЭТИ девять ситуаций различимы, но зато они неразличимы с 18-ю остальными. Поэтому он должен трижды отвечать «1», трижды называть «2» и трижды говорить тюремщику «3», всё остальное для него (а значит, и для нас — пока!) не столь существенно.
Предпримем следующую попытку найти хорошую стратегию, исходя из того, что мы написали выше. Начнём теперь не с первого, а с третьего заключённого.
Пусть третий называет сумму тех двух чисел, которые он видит на остальных, а если эта сумма больше 3 — то уменьшает ее на 3, то есть называет 1:
| Номер ситуации |
Числа на шляпах |
Ход 3-го |
| 1) | 111 | 2 |
| 2) | 112 | 2 (В) |
| 3) | 113 | 2 |
| 4) | 121 | 3 |
| 5) | 122 | 3 |
| 6) | 123 | 3 (В) |
| 7) | 131 | 1 (В) |
| 8) | 132 | 1 |
| 9) | 133 | 1 |
Это позволяет третьему выиграть (то есть правильно угадать своё число) в трех ситуациях. (Ситуации, приводящие к выигрышу заключенных, помечены буквой В.)
А если и второй будет действовать аналогично? Разумеется, он видит другие числа, поэтому и выигрывать будет в других ситуациях.
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го |
| 1) | 111 | 2 | 2 |
| 2) | 112 | 2 (В) | 3 |
| 3) | 113 | 2 | 1 (В) |
| 4) | 121 | 3 | 2 (В) |
| 5) | 122 | 3 | 3 |
| 6) | 123 | 3 (В) | 1 |
| 7) | 131 | 1 (В) | 2 |
| 8) | 132 | 1 | 3 (В) |
| 9) | 133 | 1 | 1 |
Результат выглядит, на первый взгляд, превосходно: все три выигрышных ситуации отличаются, и для успехов первого заключённого остались еще три каких-то ситуации. В них (чтобы выиграть) он должен назвать число 1.
Однако здесь самое время вспомнить, что на самом-то деле ситуаций не 9, а 27 — мы рассмотрели из них только первую треть, в которой на шляпе первого было написано число 1.
Добавим остальные две трети:
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го |
| 1) | 111 | 2 | 2 |
| 2) | 112 | 2 (В) | 3 |
| 3) | 113 | 2 | 1 (В) |
| 4) | 121 | 3 | 2 (В) |
| 5) | 122 | 3 | 3 |
| 6) | 123 | 3 (В) | 1 |
| 7) | 131 | 1 (В) | 2 |
| 8) | 132 | 1 | 3 (В) |
| 9) | 133 | 1 | 1 |
| 10) | 211 | 3 | 3 |
| 11) | 212 | 3 | 1 (В) |
| 12) | 213 | 3 (В) | 2 |
| 13) | 221 | 1 (В) | 3 |
| 14) | 222 | 1 | 1 |
| 15) | 223 | 1 | 2 (В) |
| 16) | 231 | 2 | 3 (В) |
| 17) | 232 | 2 (В) | 1 |
| 18) | 233 | 2 | 2 |
| 19) | 311 | 1 (В) | 1 (В) |
| 20) | 312 | 1 | 2 |
| 21) | 313 | 1 | 3 |
| 22) | 321 | 2 | 1 |
| 23) | 322 | 2 (В) | 2 (В) |
| 24) | 323 | 2 | 3 |
| 25) | 331 | 3 | 1 |
| 26) | 332 | 3 | 2 |
| 27) | 333 | 3 (В) | 3 (В) |
Увы... стратегия «сложим то, что видим, и назовём вслух либо сумму, либо число на 3 меньше» не работает:
Мы помним, что в первой трети выигрыши первого достигались называнием числа 1. Аналогично, во второй трети для достижения выигрыша первый должен еще на трех ситуациях назвать число 2. Но так как на последней трети выигрыши второго и третьего заключённых «совместились», то выигрывать все остальные 6 случаев должен первый. Для этого ему нужно на всех шести ситуациях называть число 3. Но он не может этого сделать, поскольку в трех случаях (из девяти неразличимых для себя) называет 1, а еще в трех — 2. Так что выигрыша на всех ситуациях 19)–27) не получается никак.
Тупик? Казавшаяся уже столь близкой победа обернулась миражом?
И да, и нет. Мы выяснили, что в задаче не получается действовать совсем прямолинейно — то есть называть то, что видишь на ком-то из остальных, а также сумму того, что увидел на обоих. Но ведь нам и не надо искать простые решения — достаточно лишь, чтобы решение РАБОТАЛО. Как можно исправить решение, приведенное выше, чтобы оно заработало? Будем исходить из того, что на первой трети оно нас устраивало. Добавим на первой трети выигрыши первого, а на двух остальных третях пока временно уберем ходы второго.
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го | Ход 1-го |
| 1) | 111 | 2 | 2 | 1 (В) |
| 2) | 112 | 2 (В) | 3 | |
| 3) | 113 | 2 | 1 (В) | |
| 4) | 121 | 3 | 2 (В) | |
| 5) | 122 | 3 | 3 | 1 (В) |
| 6) | 123 | 3 (В) | 1 | |
| 7) | 131 | 1 (В) | 2 | |
| 8) | 132 | 1 | 3 (В) | |
| 9) | 133 | 1 | 1 | 1 (В) |
| 10) | 211 | 3 | 1 (В) | 1 |
| 11) | 212 | 3 | ||
| 12) | 213 | 3 (В) | ||
| 13) | 221 | 1 (В) | ||
| 14) | 222 | 1 | 2 (В) | 1 |
| 15) | 223 | 1 | ||
| 16) | 231 | 2 | ||
| 17) | 232 | 2 (В) | ||
| 18) | 233 | 2 | 3 (В) | 1 |
| 19) | 311 | 1 (В) | 1 | |
| 20) | 312 | 1 | ||
| 21) | 313 | 1 | ||
| 22) | 321 | 2 | ||
| 23) | 322 | 2 (В) | 1 | |
| 24) | 323 | 2 | ||
| 25) | 331 | 3 | ||
| 26) | 332 | 3 | ||
| 27) | 333 | 3 (В) | 1 |
Мы видим, что в ситуациях 10), 14) и 18) ни первый, ни третий не выигрывают. Значит, в этих ситуациях должен выигрывать второй, а для этого ему необходимо называть вполне определенные числа. Это позволяет заполнить табличку некоторыми его ходами (см. выше) и продолжить ее заполнение так, как показано ниже:
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го | Ход 1-го |
| 1) | 111 | 2 | 2 | 1 (В) |
| 2) | 112 | 2 (В) | 3 | |
| 3) | 113 | 2 | 1 (В) | |
| 4) | 121 | 3 | 2 (В) | |
| 5) | 122 | 3 | 3 | 1 (В) |
| 6) | 123 | 3 (В) | 1 | |
| 7) | 131 | 1 (В) | 2 | |
| 8) | 132 | 1 | 3 (В) | |
| 9) | 133 | 1 | 1 | 1 (В) |
| 10) | 211 | 3 | 1 (В) | 1 |
| 11) | 212 | 3 | 2 | |
| 12) | 213 | 3 (В) | 3 | |
| 13) | 221 | 1 (В) | 1 | |
| 14) | 222 | 1 | 2 (В) | 1 |
| 15) | 223 | 1 | 3 | |
| 16) | 231 | 2 | 1 | |
| 17) | 232 | 2 (В) | 2 | |
| 18) | 233 | 2 | 3 (В) | 1 |
| 19) | 311 | 1 (В) | 1 | |
| 20) | 312 | 1 | ||
| 21) | 313 | 1 | ||
| 22) | 321 | 2 | ||
| 23) | 322 | 2 (В) | 1 | |
| 24) | 323 | 2 | ||
| 25) | 331 | 3 | ||
| 26) | 332 | 3 | ||
| 27) | 333 | 3 (В) | 1 |
Например, мы вписали за второго в 11) и 17) число 2, потому что с его точки зрения эти ситуации неотличимы от 14) — он видит две двойки на остальных заключённых.
Движемся дальше. Мы видим, что выигрыши в 11), 15) и 16) должны быть у первого. Значит, он должен называть двойки во всех этих случаях. Соответственно, в трёх остальных случаях у него обязаны быть тройки. Продолжим заполнение таблички:
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го | Ход 1-го |
| 1) | 111 | 2 | 2 | 1 (В) |
| 2) | 112 | 2 (В) | 3 | 2 |
| 3) | 113 | 2 | 1 (В) | 3 |
| 4) | 121 | 3 | 2 (В) | 3 |
| 5) | 122 | 3 | 3 | 1 (В) |
| 6) | 123 | 3 (В) | 1 | 2 |
| 7) | 131 | 1 (В) | 2 | 2 |
| 8) | 132 | 1 | 3 (В) | 3 |
| 9) | 133 | 1 | 1 | 1 (В) |
| 10) | 211 | 3 | 1 (В) | 1 |
| 11) | 212 | 3 | 2 | 2 (В) |
| 12) | 213 | 3 (В) | 3 | 3 |
| 13) | 221 | 1 (В) | 1 | 3 |
| 14) | 222 | 1 | 2 (В) | 1 |
| 15) | 223 | 1 | 3 | 2 (В) |
| 16) | 231 | 2 | 1 | 2 (В) |
| 17) | 232 | 2 (В) | 2 | 3 |
| 18) | 233 | 2 | 3 (В) | 1 |
| 19) | 311 | 1 (В) | 1 | |
| 20) | 312 | 1 | 2 | |
| 21) | 313 | 1 | 3 (В) | |
| 22) | 321 | 2 | 3 (В) | |
| 23) | 322 | 2 (В) | 1 | |
| 24) | 323 | 2 | 2 | |
| 25) | 331 | 3 | 2 | |
| 26) | 332 | 3 | 3 (В) | |
| 27) | 333 | 3 (В) | 1 |
Теперь осталось дозаполнить табличку выигрышами второго для ситуаций 20), 24), 25) и вписать те же числа в качестве его ответов на неразличимые (для него) строчки:
| Номер ситуации |
Числа на шляпах |
Ход 3-го | Ход 2-го | Ход 1-го |
| 19) | 311 | 1 (В) | 3 | 1 |
| 20) | 312 | 1 | 1 (В) | 2 |
| 21) | 313 | 1 | 2 | 3 (В) |
| 22) | 321 | 2 | 3 | 3 (В) |
| 23) | 322 | 2 (В) | 1 | 1 |
| 24) | 323 | 2 | 2 (В) | 2 |
| 25) | 331 | 3 | 3 (В) | 2 |
| 26) | 332 | 3 | 1 | 3 (В) |
| 27) | 333 | 3 (В) | 2 | 1 |
Ура, получилось! Мы наконец-то получили работающее решение для троих заключённых. Теперь можно приступать к его осмыслению и шлифовке. В явном виде (то есть в виде аккуратно сформулированной стратегии) оно выглядит так:
Пусть числа на шляпах троих заключённых равны x, y, z.
Стратегия-3
- За первого. Если y = z, называть 1. Если y – z = 2 или –1, называть 2. Если y – z = 1 или –2, называть 3.
- За второго. Если x – z = 1 или –2, называть 1. Если x – z = 2 или –1, называть 3. Если x = z, называть 2.
- За третьего. Если x + y < 4, называть x + y, иначе называть x + y – 3.
Почему это работает? Если бы у нас был царский путь, мы бы могли это как-нибудь объяснить, а поскольку его нет, то приходится отвечать так: «потому что мы перебрали все варианты, свели их в табличку и убедились в правильности предлагаемых ходов».
Однако как обобщить такое решение с трёх человек на 100? Эх, если бы у нас был царский путь...
Как же всё-таки решить задачу?
Попробуем отыскать разумные закономерности в тех решениях для двух и трёх заключённых, которые мы привели. Для двух заключённых (на шляпах которых выписаны числа x и y) предложенную нами стратегию можно переформулировать так: «первый всегда называет число y, а второй — число x + 1 или (x + 1) – 2».
Для трёх заключённых у нас тоже была сформулирована похожая альтернатива: либо x + y, либо x + y – 3.
В теории чисел — так сказать, «высшей арифметике» — эта альтернатива имеет специальное название «сравнение по модулю 3», а в школьной математике ее обычно называют нахождением остатка от деления на 3.
Тут же рядом был и еще один аналогичный пример: «если разность равна 1 или –2». Это значит, что остаток от деления на 3 равен 1. Аналогично, «если разность равна 2 или –1» — соответствует остатку от деления на 3, равному 2. Этот факт мы можем записать так: разность равна (2 mod 3).
Как переформулировать «стратегию-3» с использованием остатков mod 3? Для этого нужно аккуратно объединять три варианта (разности или суммы чисел, которые заключённый видит на двух остальных). При этом следует учитывать, что остатки при делении на 3 принимают значения 0, 1 или 2, а числа на шляпах — не от 0 до 2, а от 1 до 3. То есть к каждому полученному остатку нужно прибавлять 1. И вот что получается в ходе наших «плясок с бубнами».
Стратегия-3a
- За первого. Называть ((z – y) mod 3) + 1.
- За второго. Называть ((z – x + 1) mod 3) + 1.
- За третьего. Называть ((x + y + 2) mod 3) + 1.
А можно ли сделать запись более единообразной? Да, можно, но для этого придётся изменить стратегию, заменив у первого и второго z на (–z), а у третьего (с которого мы, собственно, начинали) — изменив оба числа на противоположные.
Стратегия-3b
- За первого. Называть ((–y – z) mod 3) + 1.
- За второго. Называть ((1 – z – x) mod 3) + 1.
- За третьего. Называть ((2 – x – y) mod 3) + 1.
Что здесь написано? Что каждый из заключённых держит «в уме» какой-то свой остаток — у одного это 0, у второго 1, у третьего 2. А затем каждый называет тюремщику такое слагаемое, которое в сумме с двумя остальными (то есть числами, которые этот заключённый видит на остальных) будет равно этому самому остатку «в уме». А точнее, сумма будет давать нужный остаток при делении на 3. И поскольку три остатка «в умах» у заключенных различны, а никаких других остатков нет, то какой-то один из этих остатков — правильный, то есть соответствует реальным числам на шляпах. Значит, тот из заключённых, который называет число, подбирая его под данный (правильный) остаток, тем самым правильно угадает номер на своей шляпе.
Ну а теперь уже перейти к решению задачи для 100 заключённых совсем просто. Берём и аккуратно заменяем 3 на 100. Итак, пусть есть 100 человек, и числа на их шляпах равны x1, x2, ..., x100.
Стратегия-100
- За первого. Называть ((–x2 – x3 – ... – x100) mod 100) + 1.
- За второго. Называть ((1 – x1 – x3 – ... – x100) mod 100) + 1.
- ...
- За сотого. Называть ((99 – x1 – x2 – ... – x99) mod 100) + 1.
В каждой скобке из «остатка в уме» вычитается сумма всех тех чисел, которые данный заключённый видит на остальных.
Послесловие
Согласитесь, что после преодоления всех трудностей поиска решения для трёх заключённых получить почти моментально его обобщение на 100 человек (а фактически — на произвольное количество человек N) — это очень большой успех. Можно ли было заранее догадаться, что этот результат будет именно таким? Боюсь, что нет. Можно ли было хотя бы предвидеть, что в ответе будут какие-то остатки при делении на 100? Наверное, да, но какой именно вид будет у «алгоритма действий», было совсем непонятно.
По убеждению автора, сила математических инструментов — вовсе не только в том, что математический аппарат позволяет успешно решать задачи из «смежных» областей науки, в частности из физики. Главный источник «математической силы» — это универсальность методов и приёмов. Попробую перечислить те общие приёмы, которыми мы пользовались:
- Поиск закономерностей.
- Выбор эффективных обозначений.
- Анализ и модификация неудачного решения.
- Деление задачи на случаи.
- Рассмотрение «ключевого» частного случая («специализация»).
- Использование графических и табличных величин для повышения наглядности.
- Обобщение.
Начиная решать какую-то новую задачу, математик никогда не может быть уверенным ни в том, что он сумеет довести решение до конца, ни в том, что это решение будет иметь хоть какое-то «практическое применение». Тем не менее в истории математики нередки случаи, когда совершенно абстрактные математические теории, придуманные поначалу для решения сложнейших отвлечённых задач, впоследствии оказывались востребованными и актуальными. Впрочем, это уже тема для совсем другого разговора.
-
Спасибо за задачу, с удовольствием потратил время на её решение.
Есть небольшое замечание насчет вашего решения. По-моему совершенно необязательно перебирать много вариантов "алгоритмов" для 2, 3 человек, чтобы решить задачу.
Достаточно догадаться, что раз сумма всех 100 чисел на шляпах по модулю 100 может принимать ровно сто значений (по определению), и значит каждый заключенный может сделать ставку на одно определенное значение, и один из них угадает. Таким образом, участник n делает ставку на то, что:
( A1 + A2+ ... An + ... + A100 ) mod 100 = n mod 100, и следовательно:
An=(n-1 - A1 - A2 - ... - An-1 - An+1 - ... -A100) mod 100 + 1
Это и является ответом, хотя можно использовать еще чуть более простую формулу, и она будет также выигрышной:
An=(n - A1 - a2 - ... - An-1 - An+1 - ... -A100) mod 100 +1
C уважением, Давид Есаян.
Третий игрок знает x- и y- координаты и говорит какое-то число h(x,y). Значит, множество точек, где угадал третий, будет графиком {z=h(x,y)}=M3. Ровно так же дело обстоит с угадываниями первого: {x=f(y,z)}=M1 и второго {y=g(x,z)}=M2.
Каждое из множеств Mi состоит из 9 точек, а всего их в кубе 27. Значит, пересекаться эти множества не должны --- ведь вместе они должны покрыть весь тор.
Про каждое из трёх множеств Mi у нас есть одно требование: при "протыкании" куба иголкой (прямой) вдоль i-й оси мы ровно в одной точке пересечём Mi. Потребуем даже больше: любая иголка вдоль i-й оси пересекает любое Mj (при j не обязательно равном i) ровно в одной точке. Если мы найдём одно такое множество X, то просто сдвигая его вдоль, например, вертикальной оси на 0,1,2, мы получим по построению непересекающиеся множества X0,X1,X2 (при этом ту часть множества, что вылезет за куб сверху, нужно сдвинуть на -3 обратно в куб).
Каждое из множеств Xi является графиком по любой координате. Поэтому мы сможем определить такие функции f,g,h, что X0=M1, X1=M2, X2=M3, и задача будет решена.
Остаётся придумать такое множество X, чтобы каждая переменная однозначно находилась по остальным. Проще всего решаются линейные уравнения --- вот и возьмём X={x+y+z=0 (mod 3)}.
Насколько я понял, все игроки видят игрока, дающего ответ. Тогда перед игрой заключенные выбирают товарища с условным номером "1". После того, как надзиратель дал команду "приступить к игре", каждый игрок определяет свой порядковый номер (например, по часовой стрелке) относительно заключенного номер "1". Затем каждый пытается найти свой номер на чьей-либо шляпе. Если номер найден, он просит слова. (Если таких заявок поступило несколько одновременно, надзиратель может выбрать любого.) Игрок дает любой ответ, а остальные видят сделавшего ход и теперь знают номер, увиденный им на какой-то шляпе. Теперь каждый смотрит на соседа слева и, если видит этот номер, подает заявку. Первый, получивший слово, называет любое число. Опять же, если все видят говорящего, то сосед слева берет слово и называет тот самый номер. Игра окончена за три хода.
Но. Если расклад такой, когда ни одно число не повторяется, и число на шляпе каждого равно его номеру в круе, то ни один игрок не сможет сделать первый ход. Игра зациклится. Нужен выход из цикла по тайм-ауту. О какой-либо возможности вести отсчет времени в условии задачи ничего не сказано. Игра проиграна, но вероятность выигрыша все-таки очень высока. А на практике, понятно, что если, скажем, номер "1" сосчитает про себя до 1000, и никто не сделал первый ход, то можно называть свой номер, и игра будет выиграна за один ход.
-
Еще проще. Первым выходит игрок порядковый номер которого соответствует номеру на шляпе игрока "1". Игрок "1" теперь знает свой номер.
-
Можно и за 2 хода.
Если кто-то не видит номера, который назвал первый, значит, этот номер у него. И он отвечает. Если видят все, то все молчат минуту. То есть этот номер есть хотя бы у 2 человек. Тогда тот, кто видит только один такой номер, на второй минуте может ответить. Если все молчат 2 минуты, значит, этих чисел еще больше. Через 100 минут определятся, причем отвечать будут двое.-
Мне кажется, задача детская. Вот только не понимаю, как в вашем случае толпа расслышит названный номер. Нет, узнать то она узнает, если первый заключенный на пальцах покажет остальным, какой номер он прошепчет тюремщику-идиоту.
А решение элементарно. И даже два.
1. заключенные договариваются, что первым выходит заключеный с наименьшим номером и называет тюремщику номер попытки. Естественно, с первой же попытки большинство будет смотреть на заключенного (-ых) с наименьшим номером. Тот, кто первым не выдерживает тяжести взглядов выходит и говорит "один". Второй не выдерживший гневых взоров выходит и говорит "два" и т.д.
2. (когда не видно лиц и глаз) договариваются, что первыми выходят два соседа первого номера. Третьим выходит первый номер и говорит: "первый, нах". Можно упростить, если договориться, что первым выходит ближайший правый (или, если кому нравиться - левый) сосед. Вторым выходит заключенный, у которого справа нет соседа. Следом выходят остальные 98 человек, но уже с вещами и на выход.
Если первого номера нет, то ситуация несколько усложняется: первым выходит сосед наименьшего номера. Это будет точка отсчёта - 0. Вторым выходит заключенный через столько соседей, сколько написано на шляпе у меньшего номера. Третьим выходит сосед первого, поворачивается, считает сколько осталось в промежутке между пустотами людей, прибавляет 1 и называет полученное число тюремщику. Далее все идут на выход.
-
-
-
Первым выходит игрок порядковый номер которого, отсчитанный от игрока "1", соответствует числу на единицу большему числа десятков в номере на шляпе игрока "1", вторым - номер которого кодирует число единиц в номере на шляпе игрока "1". Игрок "1" теперь знает свой номер. Но в условии не оговорено что тюремщик разрешит заключенным сообщать число в произвольном порядке.
"Тут же рядом был и еще один аналогичный пример: «если разность равна 1 или –2». Это значит, что остаток от деления на 3 равен 1. Аналогично, «если разность равна 2 или –1» — соответствует остатку от деления на 3, равному 2. Этот факт мы можем записать так: разность равна (2 mod 3).
