ВСОШ 2025, региональный этап, 11 класс, задача 7
( баллов) На островах Северного Ледовитого океана живут несколько медведей. Каждый медведь иногда совершает заплыв, переплывая с одного острова на другой. Оказалось, что за год каждый медведь совершил хотя бы один заплыв, но никакие два медведя не сделали поровну заплывов. При этом между каждыми двумя островами и был совершён ровно один заплыв: либо из в , либо из в . Докажите, что на каком-то острове и в начале, и в конце года не было медведей.
(А. Кузнецов)
Ответ
Решение. Обозначим общее число медведей через . Тогда всего заплывов сделано не менее
С другой стороны, общее число заплывов равно количеству пар островов, то есть . Таким образом, .
Посчитаем, сколько медведей было в начале и в конце года на каждом из островов. В сумме получится не более , потому что каждый медведь в начале и в конце года был на одном из островов. Поскольку , то на каком-то острове в начале и в конце года в сумме было не более одного медведя. Пусть в начале года на медведей не было, а в конце года там был ровно медведь. Тогда общее число заплывов, заканчивающихся на острове , на больше общего числа заплывов, которые на острове начинаются. Таким образом, остров был начальной или конечной точкой для нечётного числа заплывов, но это количество должно равняться , противоречие. Аналогично выясняется, что наоборот тоже не бывает, когда в начале года на острове был один медведь, а в конце года — ноль. Итого на острове и в начале, и в конце года медведей не было, что и требовалось.