Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ9

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

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

Решение

Всякое натуральное число a при подходящем n удовлетворяет соотношению nk ⇐ a < (n+1)k. Это означает, что в нашем графе есть ребро, соединяющее вершины a и (n+1)k-a. Поскольку разность (n+1)k-nk есть многочлен степени k-1, который с ростом n растет медленнее, чем nk, то для каждого 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 можно установить, используя соотношение -254 + 434 - 424 + 174 = 1:
1-390624-3028177-83519-2-…-648

Обсуждение

Аналогичным образом может быть показана связность графа при k = 5. В этом случае продвижение к последующему натуральному числу для чисел из диапазона [1..8403] можно осущеcтвлять при помощи тождества
-135 + 465 - 495 + 535 - 615 + 555 = 1.

Диапазон [1..b(k)], как правило, легко значительно уменьшить. Например, при k = 6 имеем b(k)=265720. Но среди вершин диапазона [131073..265720] не имеют меньших смежных вершин лишь вершины 262144,..,265720. Но, если x - одна из этих вершин, то из нее есть путь x>-x1-x2-x3 (где x1 = 126-x, x2 = 146-x1, x3 = 136-x2) в меньшую вершину.

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

Награды

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


 

 


Страница: [[marathon:problem_9]]

marathon/problem_9.txt · Последние изменения: 2015/10/04 18:11 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006