Пусть или

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

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

Рас­смот­рим для каж­до­го ту­ри­ста пер­вые но­ме­ров из его спис­ка. Все эти чисел раз­лич­ны, иначе два ту­ри­ста с сов­пав­шим чис­лом могут оба по­пасть в этот номер (если их преды­ду­щие но­ме­ра, ко­то­рых сум­мар­но не боль­ше все на ре­мон­те). Сле­до­ва­тель­но,

При чётном k этой оцен­ки до­ста­точ­но. В слу­чае нечётного k, если у ка­ко­го-то ту­ри­ста, ска­жем, Пети, -й номер сов­па­да­ет с каким-то из «пер­вых» но­ме­ров, ска­жем, с Ва­си­ным, то когда у Пети пер­вые но­ме­ров будут на ре­мон­те, а у Васи  — все но­ме­ра до сов­па­да­ю­ще­го с Пе­ти­ным (их не более будут на ре­мон­те, они по­па­дут в один номер. Зна­чит, все -е но­ме­ра от­лич­ны от пер­вых (хотя могут сов­па­дать друг с дру­гом), то есть

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

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

При нечётном k пред­ста­вим ко­ри­до­ры отеля как боль­шие диа­го­на­ли пра­виль­но­го 100-уголь­ни­ка: на каж­дой диа­го­на­ли по но­ме­ра, причём один номер общий для всех ко­ри­до­ров (на ри­сун­ке изоб­ра­же­на ана­ло­гич­ная кон­струк­ция для 6 ту­ри­стов и Каж­дая пара ту­ри­стов дви­га­ет­ся с про­ти­во­по­лож­ных кон­цов по сво­е­му ко­ри­до­ру. За­ме­тим, что если какой-то ту­рист дошел до цен­траль­но­го но­ме­ра, то он об­на­ру­жил ре­мон­ти­ру­ю­щих­ся но­ме­ров, по­это­му ни­ка­кой дру­гой ту­рист до цен­траль­но­го но­ме­ра не дойдёт.

Ответ: при и при