1.2 Докажите, что как бы колонии тупиков не располагались изначально, миграциями можно расселить колонии по одной на остров.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Индукция по числу вершин.
База тривиальна.
Переход. Докажем, что в любой вершине можно получить не 0. Подвесим дерево за эту вершину. Рассмотрим такой полуинвариант: сумма по всем вершинам величин 
где xi — число в вершине, di — её глубина в подвешенном дереве. Легко видеть, что каждая миграция не из корня дерева отдаёт единичку наверх и менее n на уровень вниз, то есть сумма строго увеличивается. Но всех возможных сумм конечное число, так что рано или поздно будет возможна миграция только из корня, а это значит, что там
Теперь, собственно, переход. Рассмотрим лист v, при необходимости делаем там не 0 (мы только что доказали, что это возможно). Теперь отдаём из v всё, кроме 1, его соседу u. Рассмотрим последовательность миграций, делающую единички в дереве без v (она берётся из индукционного предположения). Применим её, только перед каждой миграцией из u будем отдавать туда 1 из v.
