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


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

Сюжет 1

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

1.3 До­ка­жи­те, что число ко­ло­ний на дан­ном ост­ро­ве ни­ко­гда не пре­вы­сит ко­ли­че­ство со­сед­них с ним ост­ро­вов более, чем на 1.

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

Ре­ше­ние.

По­ка­жем, что любое до­ступ­ное рас­пре­де­ле­ние чисел на де­ре­ве можно по­лу­чить, ор­га­ни­зуя ми­гра­ции так, чтобы каж­дая ко­ло­ния ухо­ди­ла не даль­ше, чем на со­сед­ний ост­ров. Из этого сразу сле­ду­ет тре­бу­е­мое утвер­жде­ние.

До­ка­зы­ва­ем ин­дук­ци­ей по числу ми­гра­ций. База: ноль ми­гра­ций, оче­вид­на.

Пе­ре­ход. Пусть вот-вот про­изойдёт ми­гра­ция с ост­ро­ва v. По пред­по­ло­же­нию ин­дук­ции, все на­хо­дя­щи­е­ся на нем ко­ло­нии  — с него и со­сед­них ост­ро­вов. Раз можно ми­гри­ро­вать, то на ост­ро­ве

есть ко­ло­нии хотя бы с \deg v минус 1 со­сед­них ост­ро­вов; от­пра­вим их об­рат­но на свои ост­ро­ва. Если есть ко­ло­ния с остав­ше­го­ся со­сед­не­го ост­ро­ва, тоже от­пра­вим её об­рат­но, если есть своя ко­ло­ния, от­пра­вим её на любой из со­сед­них ост­ро­вов.

1

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