|
|
 |
Условие
Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвёртой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причём они "ходят" по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о стратегии заранее.)
Решение
Есть хотя бы два вагона, в каждом из которых хотя бы 9 мудрецов, иначе всего их не более чем 9 + 8·11 = 97 < 100. Значит, контролёры смогут сразу же поймать 18 мудрецов.
Покажем, что все мудрецы, кого не получится поймать сразу, не будут пойманы никогда. После появления контролёров до их первого хода каждый мудрец имеет три возможности перебежать в другой вагон. Назовём вагон хорошим, если в момент начала ходов контролёров в нём и в соседних с ним вагонах контролёров нет. В хорошем вагоне мудрец не будет пойман в первый ход контролёров.
Допустим, мудрец находится в первой половине электрички (для второй половины рассуждения симметричны) в вагоне k ≠ 1. Тогда мудрец может действовать следующим образом.
Если он может остаться на месте (то есть в соседних вагонах нет контролёров), то остаётся. Допустим, это не так.
Смотрим, есть ли контролёр в вагоне k + 2. Если есть, то с помощью перебежек k → k + 3 → k + 4 можно оказаться в хорошем вагоне.
Если нет, переместимся в вагон k + 2 и посмотрим, есть ли контролёр в одном из двух следующих вагонов. Если в обоих нет, то хорош вагон k + 3, если есть в k + 3, перебежим в k + 5, иначе перебежим в k + 5 , а потом в k + 6.
Мудрец из вагона 1 может оказаться в хорошем вагоне следующим образом.
Если в вагоне 2 есть контролёр, то он может действовать аналогично предыдущей ситуации для k = 1.
Если контролёра во 2-м вагоне нет, перебежим во 2-й вагон. Если в 3-м нет контролёров, то второй вагон нас устроит.
Если в 3-м вагоне есть контролёр, посмотрим на 4-й. Если там контролёр есть, то перебегаем в 5-й, а потом в 6-й. Если нет, перебегаем в 4-й и смотрим на следующие два. Если и там нет контролёров, идём в 5-й, если есть в 5-м – идем в 7-й, а если есть в 6-м, то возвращаемся в 1-й.
Заметим, что использовано не более трёх перебежек. И оказаться в крайнем вагоне мудрец мог только в случае, если он – в 1-м, контролёры – в 3-м и 6-м, или (для k = 6) он – в 12-м, а контролёры – в 10-м, 7-м или 10-м и 5-м. В последнем случае рассмотрим симметричную ситуацию, в которой мудрец – в вагоне 1, а контролёры – в 3-м и 6-м или 3-м и 8-м. Поэтому далее рассматриваем только мудрецов из вагонов с 1-го по 6-й.
Покажем, что делать, когда контролеры начнут ходить. Назовём активным контролера, который будет следующим ходить и пассивным того, кто только что ходил. Если мудрец видит контролёра, то он знает, является ли тот активным или пассивным: если в его поле зрения появился контролёр или контролёр совершил перемещение по вагонам, то он был активным перед прошлым перегоном, а значит, теперь будет пассивным; если он не совершал перемещения, то будет активным.
Пусть мудрец находится в одном из вагонов 3, 4, 5, 6.
Допустим, мудрец не в вагонах 2, 11. Тогда ему видно пять вагонов, а
перемещаться нельзя разве что в четыре (три из-за активного контролёра и один из-за пассивного). Тогда можно перебежать в оставшийся. Так и сделаем, если этот вагон – не 1-й. В противном случае заметим, что мудрец находится в вагоне 3, а оба контролёра – в соседних с ним вагонах, и мудрец может перебежать в вагон 6.
Допустим, мудрец находился в вагоне 2. Ему видно четыре вагона. Если среди них нет безопасного, то безопасен вагон 5, куда он и перебежит. Пусть есть безопасный.
Если это не 1-й, то перебежим туда. Допустим, безопасен только вагон 1. Если видно двух контролёров, то они в 3-м и 4-м, и можно перебежать в 5-й или остаться во 2-м (в зависимости от того, какой контролёр активен).
Если видно только одного контролёра, тогда он – в вагоне 3. Тогда сначала надо перебежать в 1-й, а после хода этого контролёра (возможно, его придётся подождать) перебежать туда, где был он (в вагон 3). Отметим, что только этот вариант предписывает действия на два хода.
Заметим, что в результате выполнения каждого из вариантов мы оказываемся не в вагоне 1. Это могло случиться только при изначальном расположении, так что контролёры расположены в 3-м и 6-м или 3-м и 8-м. Тогда мудрецу следует подождать хода контролёра из вагона 3 и тогда сразу перебежать на его место. А для начального расположения не в крайнем вагоне перебежки мудреца уже разобраны.
Итак, чтобы было поймано не больше 18 мудрецов, они должны расположиться по 8 в восьми вагонах и по 9 – еще в четырёх, а далее следовать указанному алгоритму.
Ответ
82 мудреца.
