=====ММ9=====

**Конкурсная задача ММ9** 93 баллов)

Пусть k - фиксированное натуральное число.\\
Рассмотрим граф, вершинами которого являются натуральные числа (таким образом, число вершин бесконечно).
Вершины a и b соединены ребром, если a+b есть k-тая степень некоторого натурального числа.
Доказать, что граф связен при:\\
k = 2 (2 балла);\\
k = 3 (3 балла);\\
k = 4 (4 балла).

**Решение**

Всякое натуральное число a при подходящем n удовлетворяет соотношению
n<sup>k</sup> <= a < (n+1)<sup>k</sup>. Это означает, что в нашем графе есть ребро, соединяющее вершины a и (n+1)<sup>k</sup>-a. Поскольку разность
(n+1)<sup>k</sup>-n<sup>k</sup> есть многочлен степени k-1, который с ростом n растет медленнее, чем n<sup>k</sup>, то для каждого k найдется b(k) такое, что каждое a, большее b(k), соединено ребром с меньшим числом.

Таким образом, изо всякой вершины, большей b(k), можно 'спуститься' в одну из вершин диапазона [1..b(k)]. Поэтому для доказательства связности графа достаточно показать связность некого подграфа, содержащего вершины 1,2,...b(k).
Легко видеть, что:\\
b(2) = 4;\\
b(3) = 32;\\
b(4) = 648;\\
b(5) = 8403;\\
b(6) = 265720;\\
B(7) = 5000000;\\
И т.д.

Для k = 2 соответствующий связный подграф легко строится вручную:\\
1-3-13-12-4-5-11-14-2\\
('a-b' означает, что вершины a и b соединены ребром.)

При k = 3 связность вершин 1,2,...32 легко показать, воспользовавшись соотношением -53 + 73 - 93 + 83 = 1:\\
1-124-219-510-\\
2-123-220-509-\\
3-122-221-508-\\
. . . . . . .\\
31-94-249-480-32

Аналогично при k = 4 связность вершин 1,2,...648 можно установить, используя соотношение -25<sup>4</sup> + 43<sup>4</sup> - 42<sup>4</sup> + 17<sup>4</sup> = 1:\\
1-390624-3028177-83519-2-...-648

**Обсуждение**

Аналогичным образом может быть показана связность графа при k = 5. В этом случае продвижение к последующему натуральному числу для чисел из диапазона [1..8403] можно осущеcтвлять при помощи тождества\\
-13<sup>5</sup> + 46<sup>5</sup> - 49<sup>5</sup> + 53<sup>5</sup> - 61<sup>5</sup> + 55<sup>5</sup> = 1.

Диапазон [1..b(k)], как правило, легко значительно уменьшить. Например, при k = 6 имеем b(k)=265720. Но среди вершин диапазона [131073..265720] не имеют меньших смежных вершин лишь вершины 262144,..,265720. Но, если x - одна из этих вершин, то из нее есть путь x>-x<sub>1</sub>-x<sub>2</sub>-x<sub>3</sub> (где x<sub>1</sub> = 12<sup>6</sup>-x, x<sub>2</sub> = 14<sup>6</sup>-x<sub>1</sub>, x<sub>3</sub> = 13<sup>6</sup>-x2) в меньшую вершину.

Комбинируя такие приемы и различные методы поиска на графах, легко доказать, связность графа еще для нескольких значений k.\\
Но мне (как и марафонцам, откликнувшимся на эту задачу) представлялось более интересным доказать гипотезу, что граф связен при любом k.\\
Борис Бух прислал мне набросок доказательства, а Владислав Франк, несколько позже, аккуратное доказательство этого предположения.

**Награды**

За правильное решение задачи (я не проверял работу программ, приложенных к решениям, но надеюсь, что они работают как надо) Борис Бух и Павел Егоров получают по 9 призовых баллов. Эти баллы получились после добавления поощрительных баллов за обобщение задачи на бОльшие k и вычитания части призовых баллов за упомянутую перегруженность решений информатикой. На резонные возражения, что и в решении, приведенном мной, фигурируют соотношения, полученные не без помощи компьютера (или божественного озарения), отвечу, что для понимания и проверки изложенного решения не нужно ни программировать, ни разбираться в чужих программах.
За правильное решение первого пункта и верные соображения по поводу остальных Вячеслав Пономарев получает 4 призовых балла. 
----