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