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


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

Сюжет 1

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

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

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

Ре­ше­ние.

Пред­ста­вим ар­хи­пе­лаг в виде графа. Тогда наша си­сте­ма  — де­ре­во с не­от­ри­ца­тель­ным чис­лом в каж­дой вер­ши­не (рав­ным числу ко­ло­ний на со­от­вет­ству­ю­щем ост­ро­ве); сумма всех чисел равна n. Если ми­гри­ро­вать нель­зя, каж­дое число мень­ше со­от­вет­ству­ю­щей сте­пе­ни хотя бы на еди­нич­ку. Сум­ми­руя не­ра­вен­ства по всем вер­ши­нам, по­лу­ча­ем:

 n мень­ше или равно 2 левая круг­лая скоб­ка n минус 1 пра­вая круг­лая скоб­ка минус n=n минус 2.

Про­ти­во­ре­чие.

1

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