|
||||||||||||||||||
|
Содержание160Конкурсная задача ММ160 (ТГ-5) (10 баллов)
На множестве натуральных чисел от 1 до 10460353203 структура графа G задается так:
вершины a и b смежны тогда и только тогда, когда множества цифр в g-ичной записи чисел a и b различны при любом натуральном g \ge 2.
Является ли G: Решение Положим n = 10460353203=321. Обозначим U1={2k-1|k ∈ {1,2, …, 33}}, U2=V U1. Очевидно, что числа из U1 и только они записываются в двоичной системе с помощью одних единиц. Поэтому эти 33 вершины попарно не смежны. Вершины из U2 в двоичной записи имеют нули и единицы. Соответственно и эти вершины попарно не смежны. Таким образом, граф двудольный. Не сложно найти в G изолированные вершины. Их имеет смысл искать среди чисел из U2, в троичную запись которых входят все троичные цифры. Такая вершина будет заведомо не смежна всем вершинам из U2 и большинству вершин из U1. Дело в том, что в троичную запись большинства вершин из U1 входят все троичные цифры. Исключение составляют вершины 1, 3, 7, 31, 255 и 32767. Однако вершина 1, очевидно, не смежна никакой вершине, кроме 2. Для того чтобы искомая вершина a была не смежна 3, достаточно взять число a, кратное 3 и большее 12. Тогда запись этого числа в системе счисления c основанием g = a-3 будет состоять из двух троек (*). Аналогично можно обеспечить отсутствие смежности вершинам 7, 31, 255 и 32767. Впрочем, поскольку подходящих вершин много, можно найти одну из них подбором. Легко проверяется, что наименьшей изолированной вершиной будет 87. Ясно, что в силу двудольности в графе не может быть цикла, длина которого меньше 4. В то же время цикл длины 4 (в виду огромного числа таких циклов) найти легко. Такими циклами будут, например, (2,3,4,7) или (31,88,255,70);
Подсчитаем число вершин, не смежных 3.
Покажем, что степень вершины 31 больше 10000000000. Для упрощения оценки пренебрежем возможными пересечениями множеств вершин не смежных 31.
Ответ: Граф G: Обсуждение Вершина 31 не единственная вершина, степень которой превышает 10000000000. Рассуждениями, аналогичными приведенным, можно показать, что еще большую степень имеет вершина 255. «Третье место» занимает вершина 32767. Но ее степень уже меньше 10000000000 (подвело основание 7).
Ясно, что 87, далеко не единственная изолированная вершина. Таковыми будут, например, 375, 501, 885, 1407, 1527, 1533, 1917, 3573, 3927, 3933, 6015, 6135, 7551, 7677, 8031… С подробным обоснованием вышеперечисленных и некоторых других свойств графа G можно познакомиться в :решении Олнга Полубасова. Замечу, что по ходу решения Олег «изобрел велосипед». Его теорема 9 - это известная формула для подсчета числа сюръективных отображений (в нашем случае из m-элементного множества позиций в k-элементное множество цифр). Внеся первое слагаемое под знак суммы, можно записать ее проще: Или даже так: L(m,k)=k!S(m,k), где S(m,k) - соответствующее число Стирлинга второго рода. Впрочем, «велосипед функционирует исправно». И это главное! К тому же, не мне судить Олега. В свое время, я «наступил на те же грабли» - вывел формулу для числа сюръекций и был очень доволен собой, пока не заглянул в книжку.
Число 321 в качестве количества вершин было выбрано по следующим соображениям:
Если уйти от частного случая n=321, появится много новых интересных вопросов: Замечу, что вершина 87 остается изолированной при n ≤ 102000. Не исключаю. что так будет и при любых больших n. Но боюсь, что доказать эту гипотезу настолько трудно, что проще опровергнуть Награды За правильное решение и некоторое обобщение задачи ММ160 Олег Полубасов получает 12 призовых баллов. Алексей Волошин получает 10 призовых баллов, Сергей Половинкин, Виктор Филимоненков и Анатолий Казмерчук - по 9 призовых баллов а Николай Дерюгин - 7 призовых баллов. Эстетическая оценка задачи - 4.8 балла. Разбор задачи ММ160 подготовил Владимир Лецко
|
|||||||||||||||||
|
||||||||||||||||||
|