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


Содержание

ММ27

Конкурсная задача ММ27 (12 баллов)

Эта задача перекликается с задачей №9 и отчасти с задачами ММ11 и ММ7.

Граф G задан на множестве V = {1, 2,…, n} по правилу:
вершины a и b соединены ребром, если a+b есть квадрат натурального числа.

При каком наименьшем n в G есть:
1) циклы?
2) циклы четной длины?
3) четырехвершинная клика?
4) Те же вопросы, что и в п.п. 1-3, для графа заданного на множестве V по правилу:
вершины a и b соединены ребром, если a+b есть куб натурального числа.

Напомню, что клика - это такое подмножество вершин графа, что любые две из них соединены ребром.

Решение

Обозначим через G(s,n) граф, заданный на множестве V = {1, 2,…, n}, в котором вершины a и b соединены ребром, если a+b есть s-я степень натурального числа.
Заметим, что при n > m граф G(s,n) содержит G(s,m) в качестве подграфа.

Ответ к пунктам 1 и 2 легко получается простым (ручным) перебором.
Стартуя с n = 1 и добавляя вершины и соответствующие ребра, убеждаемся, что первый цикл 1-15-10-6-3-1 появляется при n = 15.
(Отмечу, что G(2,14) - это, по-видимому, единственный нетривиальный случай, когда граф G(s,n) является деревом.)
Цикл четной длины 1-3-6-19-17-8-1 впервые возникает при n = 19.

Для отыскания циклов при s = 3 заметим, что, начиная с n = 123, количество ребер в графе G(3,n) становится не меньше количества вершин, а такие графы гарантированно имеют циклы. Поэтому возьмем граф G(3,123) и начнем удалять висячие (т.е. инцидентные только одному ребру) вершины. После удаления таких вершин, другие, не бывшие ранее висячими, вершины могут стать висячими. Удалим и их. Процесс будем продолжать до тех пор, пока висячих вершин не останется. В результате получим цикл:
1-7-20-105-111-14-13-112-104-21-6-2-62-53-1
Этот цикл возникает при n = 112 и имеет четную длину.

Теперь займемся поиском четырехвершинных клик. Пусть вершины x, y, z и t образуют клику. Тогда они удовлетворяют системе:
x + y = a
y + z = b
z + t = c
x + z = d
x + t = e
y + t = f,
где a, b, c, d, e, f - различные квадраты (кубы).
Легко видеть, что эта система разрешима тогда и только тогда, когда
a + c = b + e = d + f. (1)
Таким образом, для отыскания клики нужно найти число, представимое в виде суммы квадратов (кубов) не менее чем тремя способами. В случае разрешимости решением системы будет набор:
((a-b+d)/2, (a+b-d)/2, (-a+b+d)/2, (a-b+2c-d)/2).
Поэтому выполнения только условия (1) мало для построения клики. Необходимо, чтобы все числа набора (2) были целыми и положительными. Ясно, что в минимальном решении a, b, c, d не могут быть одновременно четны (иначе бы оно не было минимальным). Поэтому для того, чтобы все числа в (2) были целыми, надо чтобо среди чисел a, b, d было ровно одно четное.

Вопросы о представимости натуральных чисел суммой двух квадратов и количестве таких представлений не вызывают затруднений (см., например, А.А.Бухштаб. Теория чисел). Перебирая небольшие числа, имеющие достаточное количество представлений в виде суммы двух квадратов, находим, что четырехвершинная клика впервые встречается в графе G(2,n) при n = 3362. Вот эта клика: 2, 359, 482, 3362.

Значительно сложнее обстоит дело с поиском четырехвершинных клик в графах G(3,n). Я искал числа, имеющие не менее трех представлений в виде суммы двух кубов, перебором (глядя на приводимый ниже ответ легко понять, что этот перебор был существенно оптимизирован). Основная трудность заключается в том, что кубы даже близких между собой чисел отличаются весьма существенно. Поэтому достаточно сложно подыскать представление (1), удовлетворяющее условию положительности всех чисел набора (2). Сложно, но можно. Итак, впервые четырехвершинная клика встречается в графе G(3,n) при n = 51114333631. Вот эта клика:
1493580092, 2510949380, 7071213244, 51114333631.

Обсуждение

Задача очевидным образом допускает ряд обобщений. Наиболее естественное из них - обобщение вопросов задачи на случай графов G(s,n) с другими натуральными s. Можно также заняться поиском клик, имеющих более 4 вершин.
{7442, 28658, 148583, 177458, 763442} - пример пятивершинной в графе G(2,n).

Влад Франк привел очень простое доказательство утверждения:
Для любого натурального s в графах G(s,n), начиная с некоторого n, есть циклы.
Справедливо и такое утверждение: Для любого натурального s графы G(s,n), начиная с некоторого n связны.
Борис Бух прислал мне набросок доказательства, а Влад Франк, несколько позже, аккуратное доказательство этого утверждения.

В решении этой задачи я указывал (сейчас это замечание удалено), что не знаком с теорией представления натуральных чисел в виде суммы двух кубов. Борис Бух любезно указал мне книгу, в которой изложена эта теория:
Melvyn Nathanson «Additive number theory: classical bases» volume 164 of Graduate Texts in Mathematics, Springer
В частности в этой книге доказано, что для любого натурального m существуют натуральные числа, имеющие не менее m представлений в виде суммы двух кубов.

Награды

За правильный и оперативный ответ на вопросы пунктов 1-3 и первые два вопроса пункта 4, а также за ряд обобщений Влад Франк получает 8 призовых баллов. На те же вопросы, что и Влад, ответил и Павел Егоров. В его решении меньше математических рассуждений и больше программирования. Павел Егоров получает 6 призовых баллов. (Поиск четырехвершинной клики в графах G(3,n) самая трудная и поэтому самая дорогая часть задачи.)


 

 


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

marathon/problem_27.txt · Последние изменения: 2015/10/09 12:54 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006