Решение задачи 296

Условие:

Дано 100 различных натуральных чисел, взяты все 4950 попарных сумм. Какое наибольшее количество степеней пятерок может быть среди них?

Решение:

Представим задачу в виде графа, состоящего из 100 вершин. Вершины в этом графе будут соответствовать числам из условия, а между двумя вершинами будет проведено ребро если сумма чисел, стоящих в этих вершинах, является степенью пятерки. Покажем, что в этом графе нет циклов.

Пусть в этом графе нашелся цикл. Рассмотрим наибольшее число в этом цикле, обозначим его через M. Из вершины, которая соответствует числу M, выходит два ребра, состоящие в цикле. Пусть эти ребра соединяют число M с числами M₁, M₂. Без ограничения общности будем считать, что M₁<M₂<M. По условию M+M₁=5ⁿ. Так как M₂>M₁, то M+M₂≥5ⁿ⁺¹, но M+M₂<M+M<2(M+M₁). То есть M+M₂ должно хотя бы в 5 раз быть больше чем M+M₁, но с другой стороны M+M₂ больше чем M+M₁ не более чем в 2 раза. Значит, в этом графе нет циклов.

Получается, этот граф представляет из себя лес (объединение деревьев). Так как во всяком дереве количество вершин на единицу больше чем количество ребер, то в исходном графе не более 99 ребер.

Пример на 99 ребер: граф представляет бамбук (дерево, в котором степень двух вершин равна единице, а остальных двум). Числа, соответствующие вершинам: 1, 4, 21, 604,.. (aᵢ+aᵢ₊₁=5ⁱ при i≥1, a₁=1).

Ответ: 99.