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


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

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

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

Ре­ше­ние.

Про­ве­дем ре­ше­ние ин­дук­ци­ей по ко­ли­че­ству участ­ни­ков кон­фе­рен­ции. База ин­дук­ции про­ве­ря­ет­ся не­по­сред­ствен­но.

Пред­по­ло­жим, что для n участ­ни­ков утвер­жде­ние за­да­чи верно.

Пусть на кон­фе­рен­цию при­е­ха­ли n + 1 участ­ни­ков. Если каж­дый из них имеет чет­ное число зна­ко­мых, что можно оста­вить одну из ком­нат пу­стой и тре­бо­ва­ние за­да­чи будет вы­пол­не­но. По­это­му будем счи­тать, что не­ко­то­рый участ­ник А имеет нечётное ко­ли­че­ство зна­ко­мых B1, B2, …, B2k + 1. По­про­сим участ­ни­ка A на время уда­лить­ся с кон­фе­рен­ции. Кроме того, за­ста­вим любых двух его зна­ко­мых по­зна­ко­мить­ся между собой, если они пре­жде не были зна­ко­мы, и, на­про­тив, вре­мен­но пре­рвать зна­ком­ство, если они знали друг друга. По­лу­чен­ную ком­па­нию из n че­ло­век можно, по пред­по­ло­же­нию ин­дук­ции, раз­ме­стить в двух ком­на­тах так, чтобы у каж­до­го было чет­ное число зна­ко­мых в своей ком­на­те. Не ума­ляя общ­но­сти, можно счи­тать, что участ­ни­ки B1, B2, …, B2s по­па­ли в первую ком­на­ту, а B2s + 1, B2s + 2, …, B2k + 1  — во вто­рую (0 мень­ше или равно s мень­ше или равно k). Те­перь по­зо­вем об­рат­но из­гнан­но­го A и под­се­лим его в первую ком­на­ту  — он будет знать

там чет­ное число людей. При этом ко­ли­че­ство зна­ко­мых у участ­ни­ков B1, B2, …, B2s ста­нет не­чет­ным. На­ко­нец, вер­нем все зна­ком­ства между Bi (1 мень­ше или равно i мень­ше или равно 2k плюс 1) в пер­во­на­чаль­ное со­сто­я­ние. Каж­дое при­об­ре­тен­ное или по­те­рян­ное зна­ком­ство ме­ня­ет ко­ли­че­ство зна­ко­мых на еди­ни­цу. По­это­му у каж­до­го из B1, B2, …, B2s ко­ли­че­ство зна­ко­мых среди людей этого на­бо­ра по­ме­ня­ет чет­ность (и ста­нет чет­ным), а у каж­до­го из B2s + 1, B2s + 2, …, B2k + 1 по-преж­не­му оста­нет­ся чет­ным. У дру­гих участ­ни­ков, кроме A и Bi, на­бо­ры зна­ко­мых всё это время во­об­ще не ме­ня­лись. По­это­му по­лу­чен­ное раз­ме­ще­ние всех участ­ни­ков по двум ком­на­там удо­вле­тво­ря­ет усло­вию за­да­чи.