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


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

Сюжет 1

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

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

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

Ре­ше­ние.

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

За­ме­тим три факта:

1)  из каж­дой вер­ши­ны вы­хо­дит не более одной стрел­ки;

2)  на каж­дом ребре рас­по­ло­же­но не более одной стрел­ки. Дей­стви­тель­но, пусть есть есть две стрел­ки между вер­ши­на­ми u и v, они в раз­ных на­прав­ле­ни­ях. Пусть стрел­ка из u в v по­яви­лась вто­рой. Но когда она по­яв­ля­лась в u была ко­ло­ния из v, ко­то­рая от­пра­ви­лась бы об­рат­но, т. е. по на­ше­му по­стро­е­нию, не было бы ни одной из стре­лок;

3)  среди вер­шин, из ко­то­рых есть стрел­ки, но в ко­то­рые стре­лок нет, нет двух со­сед­них. Это так, по­то­му что иначе бы в де­ре­ве было два нуля рядом, а так не бы­ва­ет: по­след­няя ми­гра­ция из со­от­вет­ству­ю­щих двух вер­шин ло­ма­ет вто­рой ноль.

Всё, те­перь из каж­дой вер­ши­ны, в ко­то­рую нет стре­ло­чек, вер­толёт летит по стре­лоч­кам до упора, видно, что усло­вия за­да­чи вы­пол­ня­ют­ся.

1

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