Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
1.4 Произошло некоторое число миграций. После этого на каждый остров высадилось по орнитологу. Каждый орнитолог может перелететь на другой остров на личном вертолёте по тем же воздушным коридорам. Однако в целях безопасности в течение суток запрещено взлетать с соседних островов и пролетать дважды по одному и тому же коридору или над одним и тем же островом. Докажите, тем не менее, что некоторые орнитологи могут за сутки переместиться на другие острова, чтобы на каждом острове орнитологов и колоний тупиков оказалось поровну.
По соображению из прошлого решения можно считать, что каждая колония ушла не далее, чем на соседний остров. То, на какой остров будет отправляться каждая колония при миграции, будем выбирать, как в индукционном предположении предыдущего пункта. Нарисуем на ребре дерева стрелку, если колония переместилась между соответствующими островами, направление стрелки соответствует направлению перемещения колонии.
Заметим три факта:
1) из каждой вершины выходит не более одной стрелки;
2) на каждом ребре расположено не более одной стрелки. Действительно, пусть есть есть две стрелки между вершинами u и v, они в разных направлениях. Пусть стрелка из u в v появилась второй. Но когда она появлялась в u была колония из v, которая отправилась бы обратно, т. е. по нашему построению, не было бы ни одной из стрелок;
3) среди вершин, из которых есть стрелки, но в которые стрелок нет, нет двух соседних. Это так, потому что иначе бы в дереве было два нуля рядом, а так не бывает: последняя миграция из соответствующих двух вершин ломает второй ноль.
Всё, теперь из каждой вершины, в которую нет стрелочек, вертолёт летит по стрелочкам до упора, видно, что условия задачи выполняются.
