|
||||||||||||||||||
|
СодержаниеММ9Конкурсная задача ММ9 93 баллов)
Пусть k - фиксированное натуральное число. Решение Всякое натуральное число 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).
Легко видеть, что:
Для k = 2 соответствующий связный подграф легко строится вручную:
При k = 3 связность вершин 1,2,…32 легко показать, воспользовавшись соотношением -53 + 73 - 93 + 83 = 1:
Аналогично при k = 4 связность вершин 1,2,…648 можно установить, используя соотношение -254 + 434 - 424 + 174 = 1: Обсуждение
Аналогичным образом может быть показана связность графа при k = 5. В этом случае продвижение к последующему натуральному числу для чисел из диапазона [1..8403] можно осущеcтвлять при помощи тождества Диапазон [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. Награды За правильное решение задачи (я не проверял работу программ, приложенных к решениям, но надеюсь, что они работают как надо) Борис Бух и Павел Егоров получают по 9 призовых баллов. Эти баллы получились после добавления поощрительных баллов за обобщение задачи на бОльшие k и вычитания части призовых баллов за упомянутую перегруженность решений информатикой. На резонные возражения, что и в решении, приведенном мной, фигурируют соотношения, полученные не без помощи компьютера (или божественного озарения), отвечу, что для понимания и проверки изложенного решения не нужно ни программировать, ни разбираться в чужих программах. За правильное решение первого пункта и верные соображения по поводу остальных Вячеслав Пономарев получает 4 призовых балла.
|
|||||||||||||||||
|
||||||||||||||||||
|