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