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