сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

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

 

(Фёдор Ивлев)

Спрятать решение

Ре­ше­ние.

Пусть k=2 m или k=2 m плюс 1.

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

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

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

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

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

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

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

 

Ответ: n=100 левая круг­лая скоб­ка m плюс 1 пра­вая круг­лая скоб­ка при k=2 m и n=100 левая круг­лая скоб­ка m плюс 1 пра­вая круг­лая скоб­ка плюс 1 при k=2 m плюс 1 .