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


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

Сюжет 1

В ар­хи­пе­ла­ге есть n ска­ли­стых ост­ро­вов, на них оби­та­ют n ко­ло­ний ту́пиков (каж­дая ко­ло­ния це­ли­ком гнез­дит­ся на одном ост­ро­ве). Не­ко­то­рые пары ост­ро­вов со­еди­не­ны воз­душ­ны­ми ко­ри­до­ра­ми, причём от каж­до­го ост­ро­ва до лю­бо­го дру­го­го есть ровно один путь по этим ко­ри­до­рам. Ост­ро­ва, со­единённые ко­ри­до­ром, счи­та­ют­ся со­сед­ни­ми. Ино­гда про­ис­хо­дят ми­гра­ции: с не­ко­то­ро­го ост­ро­ва на каж­дый со­сед­ний пе­ре­се­ля­ет­ся по ко­ло­нии ту­пи­ков.

1.2 До­ка­жи­те, что как бы ко­ло­нии ту­пи­ков не рас­по­ла­га­лись из­на­чаль­но, ми­гра­ци­я­ми можно рас­се­лить ко­ло­нии по одной на ост­ров.

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

Ре­ше­ние.

Ин­дук­ция по числу вер­шин.

База три­ви­аль­на.

Пе­ре­ход. До­ка­жем, что в любой вер­ши­не можно по­лу­чить не 0. Под­ве­сим де­ре­во за эту вер­ши­ну. Рас­смот­рим такой по­лу­ин­ва­ри­ант: сумма по всем вер­ши­нам ве­ли­чин x_i n в сте­пе­ни левая круг­лая скоб­ка минус d_i пра­вая круг­лая скоб­ка , где xi  — число в вер­ши­не, di  — её глу­би­на в под­ве­шен­ном де­ре­ве. Легко ви­деть, что каж­дая ми­гра­ция не из корня де­ре­ва отдаёт еди­нич­ку на­верх и менее n на уро­вень вниз, то есть сумма стро­го уве­ли­чи­ва­ет­ся. Но всех воз­мож­ных сумм ко­неч­ное число, так что рано или позд­но будет воз­мож­на ми­гра­ция толь­ко из корня, а это зна­чит, что там не 0.

Те­перь, соб­ствен­но, пе­ре­ход. Рас­смот­рим лист v, при не­об­хо­ди­мо­сти де­ла­ем там не 0 (мы толь­ко что до­ка­за­ли, что это воз­мож­но). Те­перь отдаём из v всё, кроме 1, его со­се­ду u. Рас­смот­рим по­сле­до­ва­тель­ность ми­гра­ций, де­ла­ю­щую еди­нич­ки в де­ре­ве без v (она берётся из ин­дук­ци­он­но­го пред­по­ло­же­ния). При­ме­ним её, толь­ко перед каж­дой ми­гра­ци­ей из u будем от­да­вать туда 1 из v.

1

1.1 До­ка­жи­те, что в любой мо­мент может про­изой­ти ми­гра­ция.