В отель ночью приехали 100 туристов. Они знают, что в отеле есть одноместные номера из которых k на ремонте (но неизвестно какие), а остальные свободны. Туристы могут заранее договориться о своих действиях, после чего по очереди уходят заселяться: каждый проверяет номера в любом порядке, находит первый свободный номер не на ремонте и остаётся там ночевать. Но туристы не хотят беспокоить друг друга: нельзя проверять номер, куда уже кто-то заселился. Для каждого k укажите наименьшее n, при котором туристы гарантированно смогут заселиться, не потревожив друг друга.
(Фёдор Ивлев)
Пусть или
Алгоритм. Мысленно разделим номера на 100 участков по номеров, а в случае нечётного k оставшийся номер объявим запасным. Пусть i-й турист сначала проверяет все номера i-го участка, двигаясь слева направо, потом идёт в запасной номер (если тот есть), а потом проверяет номера -го участка, но справа налево (если проверяет 1-й участок). Никакие два туриста не попадут при этом в один номер, так как суммарно на двух их участках (включая запасной номер, если он есть), всего номера.
Оценка. Для того чтобы каждый
Рассмотрим для каждого туриста первые номеров из его списка. Все эти чисел различны, иначе два туриста с совпавшим числом могут оба попасть в этот номер (если их предыдущие номера, которых суммарно не больше все на ремонте). Следовательно,
При чётном k этой оценки достаточно. В случае нечётного k, если у какого-то туриста, скажем, Пети,
Замечание. Для чётного числа туристов (а их у нас 100), алгоритм можно описать несколько иначе. При чётном k мысленно представим план отеля как 50 коридоров, в каждом из которых вдоль одной стены расположены двери номеров. Каждой паре туристов «отдадим» один коридор по которому они двигаются с противоположных концов, проверяя все встреченные комнаты. В сумме эта пара может обнаружить не более k ремонтирующихся номеров, поэтому два свободных номера для них останутся.
При нечётном k представим коридоры отеля как большие диагонали правильного 100-угольника: на каждой диагонали по номера, причём один номер общий для всех коридоров (на рисунке изображена аналогичная конструкция для 6 туристов и Каждая пара туристов двигается с противоположных концов по своему коридору. Заметим, что если какой-то турист дошел до центрального номера, то он обнаружил ремонтирующихся номеров, поэтому никакой другой турист до центрального номера не дойдёт.
Ответ: при и при