|
||||||||||||||||||
|
СодержаниеММ27Конкурсная задача ММ27 (12 баллов) Эта задача перекликается с задачей №9 и отчасти с задачами ММ11 и ММ7.
Граф G задан на множестве V = {1, 2,…, n} по правилу:
При каком наименьшем n в G есть: Напомню, что клика - это такое подмножество вершин графа, что любые две из них соединены ребром. Решение
Обозначим через G(s,n) граф, заданный на множестве V = {1, 2,…, n}, в котором вершины a и b соединены ребром, если a+b есть s-я степень натурального числа.
Ответ к пунктам 1 и 2 легко получается простым (ручным) перебором.
Для отыскания циклов при s = 3 заметим, что, начиная с n = 123, количество ребер в графе G(3,n) становится не меньше количества вершин, а такие графы гарантированно имеют циклы. Поэтому возьмем граф G(3,123) и начнем удалять висячие (т.е. инцидентные только одному ребру) вершины. После удаления таких вершин, другие, не бывшие ранее висячими, вершины могут стать висячими. Удалим и их. Процесс будем продолжать до тех пор, пока висячих вершин не останется.
В результате получим цикл:
Теперь займемся поиском четырехвершинных клик. Пусть вершины x, y, z и t образуют клику. Тогда они удовлетворяют системе: Вопросы о представимости натуральных чисел суммой двух квадратов и количестве таких представлений не вызывают затруднений (см., например, А.А.Бухштаб. Теория чисел). Перебирая небольшие числа, имеющие достаточное количество представлений в виде суммы двух квадратов, находим, что четырехвершинная клика впервые встречается в графе G(2,n) при n = 3362. Вот эта клика: 2, 359, 482, 3362.
Значительно сложнее обстоит дело с поиском четырехвершинных клик в графах G(3,n). Я искал числа, имеющие не менее трех представлений в виде суммы двух кубов, перебором (глядя на приводимый ниже ответ легко понять, что этот перебор был существенно оптимизирован). Основная трудность заключается в том, что кубы даже близких между собой чисел отличаются весьма существенно. Поэтому достаточно сложно подыскать представление (1), удовлетворяющее условию положительности всех чисел набора (2). Сложно, но можно. Итак, впервые четырехвершинная клика встречается в графе G(3,n) при n = 51114333631. Вот эта клика: Обсуждение
Задача очевидным образом допускает ряд обобщений. Наиболее естественное из них - обобщение вопросов задачи на случай графов G(s,n) с другими натуральными s. Можно также заняться поиском клик, имеющих более 4 вершин.
Влад Франк привел очень простое доказательство утверждения:
В решении этой задачи я указывал (сейчас это замечание удалено), что не знаком с теорией представления натуральных чисел в виде суммы двух кубов. Борис Бух любезно указал мне книгу, в которой изложена эта теория: Награды За правильный и оперативный ответ на вопросы пунктов 1-3 и первые два вопроса пункта 4, а также за ряд обобщений Влад Франк получает 8 призовых баллов. На те же вопросы, что и Влад, ответил и Павел Егоров. В его решении меньше математических рассуждений и больше программирования. Павел Егоров получает 6 призовых баллов. (Поиск четырехвершинной клики в графах G(3,n) самая трудная и поэтому самая дорогая часть задачи.)
|
|||||||||||||||||
|
||||||||||||||||||
|