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


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

Сюжет 2

Шары с но­ме­ра­ми от 1 до 800 по­ров­ну раз­ло­же­ны по N со­су­дам не­из­вест­ным фо­кус­ни­ку об­ра­зом. Он от­да­ет ко­ман­ды вида «по­ме­няй­те шары с но­ме­ра­ми i и j», после чего ас­си­стент ме­ня­ет их, если они и вправ­ду в раз­ных со­су­дах (иначе ни­че­го не про­ис­хо­дит). После не­сколь­ких ко­манд фо­кус­ник оста­нав­ли­ва­ет­ся.

2.1 Пусть N  =  2. До­ка­жи­те, что фо­кус­ник га­ран­ти­ро­ван­но может до­бить­ся того, чтобы в итоге хотя бы один шар ока­зал­ся не в своем из­на­чаль­ном со­су­де.

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

Ре­ше­ние.

Будем ме­нять ме­ста­ми 1 и 2, 2 и 3, 3 и 4, ... 500 и 501. Ясно, что тут встре­ча­ют­ся шары из обоих со­су­дов. Пусть k,  k плюс 1  — пер­вая пара со­сед­них шаров из раз­ных со­су­дов. Тогда мы их дей­стви­тель­но по­ме­ня­ем, а даль­ше k ме­нять­ся ни с кем не будет.

1

2.2 Пусть N  =  400. До­ка­жи­те, что фо­кус­ник может до­бить­ся того, чтобы га­ран­ти­ро­ван­но более по­ло­ви­ны шаров ле­жа­ли не в своём со­су­де.