Туристы и свободные номера в отеле

Пусть $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$.