Задача 66904

Темы:    [ Теория алгоритмов (прочее) ] [ Кооперативные алгоритмы ] [ Оценка + пример ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Ивлев Ф.

В отель ночью приехали $100$ туристов. Они знают, что в отеле есть одноместные номера $1$, $2, \ldots, n$, из которых $k$ на ремонте (но неизвестно какие), а остальные свободны. Туристы могут заранее договориться о своих действиях, после чего по очереди уходят заселяться: каждый проверяет номера в любом порядке, находит первый свободный номер не на ремонте и остаётся там ночевать. Но туристы не хотят беспокоить друг друга: нельзя проверять номер, куда уже кто-то заселился. Для каждого $k$ укажите наименьшее $n$, при котором туристы гарантированно смогут заселиться, не потревожив друг друга.

Решение

Пусть $k=2m$ или $k=2m+1$.

Алгоритм. Мысленно разделим номера на 100 участков по $m+1$ номеров, а в случае нечётного $k$ оставшийся номер объявим запасным. Пусть $i$-й турист сначала проверяет все номера $i$-го участка, двигаясь слева направо, потом идёт в запасной номер (если тот есть), а потом проверяет номера $(i+1)$-го участка, но справа налево (если $i=100$, проверяет 1-й участок). Никакие два туриста не попадут при этом в один номер, так как суммарно на двух их участках (включая запасной номер, если он есть), всего $k+2$ номера.

Оценка. Для того чтобы каждый из 100 туристов мог гарантированно заселиться в номер не на ремонте, он должен с самого начала иметь список из $k+1$ различных номеров, в которые будет заходить. Можно считать, что списки не меняются по ходу заселения других туристов (поскольку никакой информации о них мы не узнаём).

Рассмотрим для каждого туриста первые $m+1$ номеров из его списка. Все эти $100(m+1)$ чисел различны, иначе два туриста с совпавшим числом могут оба попасть в этот номер (если их предыдущие номера, которых суммарно не больше $m+m=2m$, все на ремонте). Следовательно, $n\geqslant100(m+1)$.

При чётном $k$ этой оценки достаточно. В случае нечётного $k$, если у какого-то туриста, скажем, Пети, $(m+2)$-й номер совпадает с каким-то из $100(m+1)$ «первых» номеров, скажем, с Васиным, то когда у Пети первые $m+1$ номеров будут на ремонте, а у Васи – все номера до совпадающего с Петиным (их не более $m$) будут на ремонте, они попадут в один номер. Значит, все $(m+2)$-е номера отличны от $100(m+1)$ первых (хотя могут совпадать друг с другом), то есть $n\geqslant100(m+1)+1$.

Ответ

$n = 100(m+1)$ при $k=2m$ и $n = 100(m+1)+1$ при $k=2m+1$.

Замечания

Для чётного числа туристов (а их у нас 100), алгоритм можно описать несколько иначе.

При чётном $k$ мысленно представим план отеля как 50 коридоров, в каждом из которых вдоль одной стены расположены двери $k + 2$ номеров. Каждой паре туристов «отдадим» один коридор по которому они двигаются с противоположных концов, проверяя все встреченные комнаты. В сумме эта пара может обнаружить не более $k$ ремонтирующихся номеров, поэтому два свободных номера для них останутся.

При нечётном $k$ представим коридоры отеля как большие диагонали правильного 100-угольника: на каждой диагонали по $k + 2$ номера, причём один номер общий для всех коридоров (на рисунке изображена аналогичная конструкция для 6 туристов и $k = 5$). Каждая пара туристов двигается с противоположных концов по своему коридору. Заметим, что если какой-то турист дошел до центрального номера, то он обнаружил $\frac{k+1}2$ ремонтирующихся номеров, поэтому никакой другой турист до центрального номера не дойдёт.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
год/номер
Номер	42
Дата	2020/21
вариант
Вариант	весенний тур, сложный вариант, 8-9 класс
задача
Номер	6
олимпиада
Название	Турнир городов
год/номер
Номер	42
Дата	2020/21
вариант
Вариант	весенний тур, сложный вариант, 10-11 класс
задача
Номер	5