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

Решение

Всякое натуральное число a при подходящем n удовлетворяет соотношению
n^k <= a < (n+1)^k. Это означает, что в нашем графе есть ребро, соединяющее вершины a и (n+1)^k-a. Поскольку разность
(n+1)^k-n^k есть многочлен степени k-1, который с ростом n растет медленне, чем n^k, то для каждого 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 легко показать, воспользовавшись соотношением -5³ + 7³ - 9³ + 8³ = 1:
1-124-219-510-
2-123-220-509-
3-122-221-508-
. . . . . . .
31-94-249-480-32
Аналогично при k = 4 связность вершин 1,2,...648 можно установить, используя соотношение -25⁴ + 43⁴ - 42⁴ + 17⁴ = 1:
1-390624-3028177-83519-2-...-648

Обсуждение

Аналогичным образом может быть показана связность графа при k = 5. В этом случае продвижение к последующему натуральному числу для чисел из диапазона [1..8403] можно осущеcтвлять при помощи тождества
-13⁵ + 46⁵ - 49⁵ + 53⁵ - 61⁵ + 55⁵ = 1
Диапазон [1..b(k)], как правило, легко значительно уменьшить. Например, при k = 6 имеем b(k)=265720. Но среди вершин диапазона [131073..265720] не имеют меньших смежных вершин лишь вершины 262144,..,265720. Но, если x - одна из этих вершин, то из нее есть путь x0-x1-x2-x3 (где x1 = 12⁶-x, x2 = 14⁶-x1, x3 = 13⁶-x2) в меньшую вершину.
Комбинируя такие приемы и различные методы поиска на графах, легко доказать, связность графа еще для нескольких значений k.
Но мне (как и марафонцам, откликнувшимся на эту задачу) представлялось более интересным доказать гипотезу, что граф связен при любом k.
Борис Бух прислал мне набросок доказательства, а Владислав Франк, несколько позже, аккуратное доказательство этого предроложения.

Награды

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