Обсуждение и разбор марафонских задач

[maxal]

VAL в сообщении #172582 писал(а):

При возведении в степень $k$ цикл длины $m$ распадается на $(k,m)$ циклов длины $m/(k,m)$. Учитывая это соображение и количество подстановок каждого циклового вида в группах $S_n$ при малых $n$ можно получить следующие $20$ значений $s(n,k)$ (если значение получается при разных наборах значений $n$ и $k$, указан один из таких наборов):

$1$ (при $n = 1, k = 1$)
$2$ (при $2 = 1, k = 1$)
$3$ (при $n = 3, k = 2$)
$4$ (при $n = 3, k = 3$)
$6$ (при $n = 3, k = 1$)
$9$ (при $n = 4, k = 9$)
$12$ (при $n = 4, k = 2$)
$16$ (при $n = 4, k = 3$)
$21$ (при $n = 5, k = 30$)
$24$ (при $n = 4, k = 1$)
$25$ (при $n = 5, k = 12$)
$36$ (при $n = 5, k = 10$)
$40$ (при $n = 5, k = 6$)
$45$ (при $n = 5, k = 4$)
$46$ (при $n = 6, k = 30$)
$56$ (при $n = 5, k = 15$)
$60$ (при $n = 5, k = 2$)
$80$ (при $n = 5, k = 3$)
$81$ (при $n = 6, k = 20$)
$96$ (при $n = 5, k = 5$)

Пара из объявленных $n,k$ не соответствуют действительности:
$|s(4,9)|=16\ne 9$, должно быть $9=|s(4,4)|$
$|s(5,30)|=16\ne 21$, должно быть $21=|s(5,20)|$

А вот значения элементов последовательности вплоть до $10^4$:
1, 2, 3, 4, 6, 9, 12, 16, 21, 24, 25, 36, 40, 45, 46, 56, 60, 80, 81, 96, 106, 120, 126, 145, 190, 225, 256, 270, 351, 400, 505, 576, 610, 666, 720, 721, 826, 855, 946, 1071, 1072, 1170, 1225, 1233, 1330, 1338, 1345, 1386, 1450, 1575, 1576, 1792, 1890, 2080, 2241, 2800, 2920, 3025, 3186, 3312, 3970, 4032, 4320, 4488, 4726, 5040, 5265, 5370, 5761, 5866, 6210, 6993, 7098, 7105, 7210, 7336, 8520, 8680
Отличия с текущей A155510:
нет элемента 105 - чему он соответствует?
есть новые элементы:
$126 = |s(6,10)|$
$145 = |s(6,12)|$
$270 = |s(6,2)|$
ну и все что больше 351

[VAL]

maxal писал(а):

Пара из объявленных $n,k$ не соответствуют действительности:
$|s(4,9)|=16\ne 9$, должно быть $9=|s(4,4)|$
$|s(5,30)|=16\ne 21$, должно быть $21=|s(5,20)|$

Конечно! В моих черновиках, и письмах участников Марафона, приславших решения этого пункта, все так и есть.
Каким образом числа 4 и 20 трансформировались в 9 и 30, мне неизвестно. По данному факту проводится проверка

Цитата:

А вот значения элементов последовательности вплоть до $10^4$:
1, 2, 3, 4, 6, 9, 12, 16, 21, 24, 25, 36, 40, 45, 46, 56, 60, 80, 81, 96, 106, 120, 126, 145, 190, 225, 256, 270, 351, 400, 505, 576, 610, 666, 720, 721, 826, 855, 1071, 1072, 1170, 1225, 1330, 1338, 1386, 1450, 1575, 1576, 1792, 1890, 2080, 2800, 2920, 3186, 3312, 4032, 4320, 4488, 5040, 5370, 5866, 6210, 6224, 6714, 7098, 7210, 7336, 8520, 8680
Отличия с текущей A155510:
нет элемента 105 - чему он соответствует?

Он соответствует элементу 145. Преобразование 145 в 105 наверняка произшло не без участия потусторонних сил.

Цитата:

есть новые элементы:
$126 = |s(6,10)|$

Здесь ничего никуда не преобразовывалось. Просто пропустил при переписывании

Цитата:

$145 = |s(6,12)|$

См. выше

Цитата:

$270 = |s(6,2)|$

В моих черновиках записано $|s(6,2)|=360$. Потерял цикловой вид $4-2$ и решил, что для $n=6$ подстановка является квадратом тогда и только тогда, когда она четна. Поэтому просто поделил $6!$ попалм. (И это при том, что у меня была программка, рассчитывающая значения $|s(n,k)|$ при малых $n$ перебором).

Ответственность за потерю 270 со мной по праву должен разделить Алексей Волошин. Он тоже потерял 270. Вот и верь после этого людям!

[ha]

Надо было все программой считать и без перебора.

[VAL]

Решения заданий "Конкурса вне конкурса" только-только начали поступать...
А тут неожиданно подкрался deadline!

[VAL]

Надеждам тех, кто пытался увильнуть от участия в "Конкурсе вне конкурса", сбыться не суждено
Идя навстречу занятым конкурсантам (не писать же "тугодумам" ), я продлеваю срок приема решений до 25.02.09

[VAL]

КОНКУРС вне КОНКУРСА

В каждой задаче тематического конкурса требовалось указать правило, по которому строится данная последовательность натуральных чисел.

Решение и Обсуждение

Конкурс "Поиск закономерности - 2" не вызвал большого ажиотажа.
Но дальше тянуть с подведением итогов смысла нет: все равно, новые решения не поступают.

Напомню, что цена задания определялась в зависимости от количества участников, справившихся с ним.
===============

1) 6, 15, 35, 77, 91, 143, 187, 209,...

Эта последовательность планировалсь как утешительная (утешились не все )
Но есть один нюанс: существует, как минимум, два вполне естественных описания, приводящих к похожим, но разным продолжениям.

а) произведения pq двух простых чисел, таких что $p < q < 2p$

б) для каждого из последовательных простых чисел $p$, выписываются его произведения на простые числа $q$, превосходящие $p$, не более, чем в 2 раза.

Может показаться, что оба описания задают одну и ту же последовательность, но на самом деле последовавательности a) и б) будут отличаться порядком членов.
Так, продолжение а) - 221, 247, 299, 323, 391, 437, 493, 527,...
А продолжение б) - 221, 247, 299, 323, 391, 493, 527, 437,...

Конкурсанты предлагали и вариант а), и вариант б). Но никто из них не описал оба продолжения (и не получил дополнительных баллов). Зато встречались описания, не соответствующие приведенным членам

Цена задачи - 5 баллов
===============

2) 1, 1, 1, 2, 1, 3, 3, 2, 4, 4, 2, 7, 5, 4, 6, 6, 2, 12, 7, 6, 8, 8, 4, 15, 9, 6, 13,...

Это последовательность троек чисел: $f(3n-2) = n, f(3n-1) = \varphi(n), f(3) = \sigma(n)$, где $\varphi(n)$ - функция Эйлера, а $\sigma(n)$ - сумма натуральных делителей.

Цена задачи - 6 баллов
===============


3) 71, 431, 719, 1511,...

Эта последовательность допускает несколько описаний, чем и не преминули воспользоваться конкурсанты. При этом авторского описания (простые числа на 10 меньшие квадратов) не
предложил никто.
Зато были предложены варианты "простые числа вида $36n(n+1)-1$" и "простые числа, представимые в виде $n(n+4)-6$", равносильные авторскому решенеию, а также вариант "простые числа вида $72n-1$, при удалении последней цифры которых они остаются простыми", приводящей к другой последовательности с тем же началом.

Цена задачи - 6 баллов
===============


4) 136, 244, 2178, 6514, 58618, 76438,...

Последовательность состоит из пар чисел:
$1^3 + 3^3 + 6^3 = 244, 2^3 + 4^3 + 4^3 = 136;$
$2^4 + 1^4 + 7^4 + 8^4 = 6514, 6^4 + 5^4 + 1^4 + 4^4 = 2178;$
$5^5 + 8^5 + 6^5 + 1^5 + 8^5 = 76438, 7^5 + 6^5 + 4^5 + 3^5 + 8^5 = 58618.$
Дальше идут числа 2755907 и 6586433, равные суммам 7-х степеней цифр друг друга.

Эта последовательность предложена Эдвардом Туркевичем.
Было это еще в октябре и мне, казалось, что еще тогда я проверил ее на предмет наличия в OEIS. Но только казалось Данная последовательность имеется в OEIS по номером A101335.

Цена задачи - 5 баллов (с учетом наличия в OEIS)
===============


5) 2, 5, 11, 19, 30, 44, 62, 85, 115, 155, 210, 288,...

$f(n) = n^2 + F(n)$, где $F(n)$ - $n$-е число Фибоначчи.

В первоначальное условие этого задания вкралсь ошибка. Но это не помешало Матвей Котову справиться с заданием, а заодно указать мне на допущенный ляп и получить бонусные баллы (решившие, в итоге, судьбу первого места).

Цена задачи - 6 баллов
===============


6) 1, 3, 13, 61, 321,...

Эта последовательность оказалась одной из самых интересных.
Авторское решение: $f(1) = 1, f(n) = n \cdot f(n-1) + (n-1)^2$.
Однако возможно и такое описание: $f(n) = \sum_{k=0}^n \frac{n!}{k!} - n.$
И даже такое: $f(n) = e \cdot \Gamma(n+1,1) - n$.

Цена задачи - 6 баллов
===============


7) 1, 2, 21, 224, 2521, 31446, 345621, 3845668, 43046721,...

Эта последовательность предложена Алексеем Изваловым. Он верно предположил, что ключом к разгадке может стать последнее из приведенных чисел. В самом деле, бросается в глаза, что $43046721 = 3^{16}.$ Правда, для понимания принципа образования последовательности важнее, что это $9^8.$
А общее правило таково: $f(n)$ есть число $n^{n-1}$, записанное в системе счисления
с основанием $n+1$.

Цена задачи - 7 баллов
===============


8) 2, 65, 72, 128, 250, 370, 468, 520, 637, 730,...

Это числа, каждое из которых представлятся одновременно суммой двух натуральных квадратов и суммой двух натуральных кубов.

Цена задачи - 7 баллов
===============


9) 5, 13, 271, 7159,...

Я полагал, что два последних задания конкурса практически не берутся. Но недооценил интеллектуальной и компьютерной мощи участников конкурса. В частности, не учел того, что в OEIS имеется возможность искать не только "куски" последовательностей, идущие подряд, но и произвольные подпоследовательности.

Последовательность из 9-го задания - это простые числа из A076408.
Поясню подробнее.
Выпишем натуральные числа, являющииеся нетривиальными (больше первой) степенями натуральных чисел: 1, 4, 8, 9, 16, 25, 27, 32, 36,...
Суммируя начальные отрезки этой последовательности будем получать члены A076408. Те из них, которые являются простыми входят в нашу последовательность.

Цена задачи - 7 баллов
===============


10) 7, 13, 15, 21, 26, 31, 40, 42, 43, 57, 62, 63, 73, 80, 85, 86, 91, 93, 111,
114, 121,...

Это числа, которые в некоторой системе счисления записываются набором из не менее чем трех одинаковых цифр. (Ясно, что двумя одинаковыми цифрами записывается любое число, начиная с 2.)

Цена задачи - 7 баллов
===============


Итоги конкурса "Поиск закономерности - 2"
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|c|} \hline № & Участники & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \Sigma\\ \hline 1. & Матвей Котов & 5 & 6 & 6 & 5 & 8 & 6 & 7 & 7 & 7 & 7 & 64\\ \hline 2. & Алексей Волошин & 5 & 6 & 6 & 5 & 6 & 6 & 7 & 7 & 7 & 7 & 62\\ \hline 3. & Николай Дерюгин & 5 & & & & 6 & 6 & & & & & 17\\ \hline 4. & Алексей Извалов & 5 & & & & & & 7 & & & & 12\\ \hline 5. & Андрей Халявин & & & 6 & & & & & & & & 6\\ \hline 5. & Владимир Боровских & & 6 & & & & & & & & & 6\\ \hline 7. & Эдвард Туркевич & & & & 5 & & & & & & & 5\\ \hline 8. & Daogiauvang & 2 & & & & & & & & & & 2\\ \hline \end{tabular}

Учитывая, что первые два призера справились со всеми заданиями и далеко оторвались от преследователей, а также то, что преимущество Матвея перед Алексеем добыто лишь за счет дополнительных показателей, объявляю лауретами конкурса Матвея Котова и Алексея Волошина.
С чем их и поздравляю!

Победителям даруется пожизненное право (и почетная обязанность) бесплатного участия во всех последующих турах Математического марафона!

===============

[VAL]

В связи с обнаружением пары писем, заблудившихся в дебрях моих устаревших адресов, вношу изменения в таблицу результатов КОНКУРСА вне КОНКУРСА.

Текущие окончательные итоги конкурса выглядят так:

"Поиск закономерности - 2"
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|c|} \hline № & Участники & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \Sigma\\ \hline 1. & Матвей Котов & 5 & 6 & 6 & 5 & 8 & 6 & 7 & 7 & 7 & 7 & 64\\ \hline 2. & Алексей Волошин & 5 & 6 & 6 & 5 & 6 & 6 & 7 & 7 & 7 & 7 & 62\\ \hline 3. & Николай Дерюгин & 5 & & & & 6 & 6 & & & & & 17\\ \hline 4. & Алексей Извалов & 5 & & & & & & 7 & & & & 12\\ \hline 5. & Виктор Филимоненков & 5 & & & & & 6 & & & & & 11\\ \hline 6. & Андрей Халявин & & & 6 & & & & & & & & 6\\ \hline 6. & Владимир Боровских & & 6 & & & & & & & & & 6\\ \hline 8. & Эдвард Туркевич & & & & 5 & & & & & & & 5\\ \hline 9. & Daogiauvang & 2 & & & & & & & & & & 2\\ \hline \end{tabular}

[VAL]

VAL писал(а):

Обращаю внимание старожилов и новичков на существенное нововведение.
Начиная с 11-го тура, победителю тура будет вручаться денежный приз (ориентировочно 10 000 рублей). Призовой фонд будет формироваться за счет штрафов за решения, содержащие грубые ошибки, а также отказ от участия в Марафоне.

В связи с наступлением второго апреля вопрос с выдачей призов временно отложен.
Все остальное, опубликованное вчера в теме "Математический марафон", остается в силе.

Шквала писем в связи с "переводом Марафона на коммерческме рельсы" не ожидал. Но думал, хоть кто-то отклитнется. Ан нет!
Никто даже не поинтересовался на какой адрес штрафы за нерешенные задачи высылать

[VAL]

В связи со вновь открывшимися обстоятельствами (не связанными с финансовым кризисом и заседанием 20-ки) цена задачи 101 увеличена до 8 баллов.
Налетай, подорожало!

[VAL]

Срок приема решений задачи ММ101 продлен до 24.04.09

[VAL]

Решения задач 11-го тура Математического марафона поступают. Но вяло.
Поэтому срок прием решений еще раз продлен:
для ММ101 до 30.04.09:
для ММ102 до 1.05.09.
Авось, еще кто-нибудь добавится к списку героев.

[VAL]

Наконец-то начали поступать решения задач 11-го тура.
Может быть, следовало еще немного подождать с разбором, чтобы решений стало побольше...
Но, боюсь, при таком развитии событий участники Марафона совсем перестанут реагировать на сроки приема решений, ожидая очередного их продления. Поэтому я решил таки опубликовать разбор задач ММ101-ММ104.

================

Баллы, полученные за решение задачи 101 учитываются дважды: в основном Марафоне и в тематическом конкурсе.

Задача 101 является прямым продолжением задачи ММ57.

ММ101 (КГ-1) (8 баллов)

Назовем многоугольник ординарным, если он выпуклый и никакие 3 его диагонали не пересекаются в одной точке внутри многоугольника. Пусть n - число сторон ординарного многоугольника. Ординарный многоугольник разбивается своими диагоналями на многоугольники, которые мы будем называть элементарными.
Начиная с какого n, число элементарных четырехугольников может превысить число элементарных треугольников?

Решение

При n = 9 требуемым многоугольником будет, например, девятиугольник с вершинами $A(0;0), B(1;0), C(50;49),D(50;53), E(3;99), F(1;100), G(-2;100), H(-50;51), I(-50;47)$. В его разбиении участвуют 67 треугольников, 69 четырехугольников и 18 пятиугольников.

Остается показать, что при n < 9 в разбиении ординарнрого (да и любого выпуклого) n-угольника треугольников больше, чем четырехугольников.
Для n < 8 это очевидно.
Пусть n = 8.
Своими диагоналями ординарный восьмиугольник разбивается на 91 часть (обоснование можно посмотреть в разборе задачи ММ57). 40 элементарных многоугольников, имеющих общую вершину с исходным многоугольником, являются треугольниками. На остальные 51 элементарных многоугольников приходится 208
углов, что пока не исключает возможности превышения четырехугольников над треугольниками.

Зафиксируем одну вершину исходного восьмиугольника вместе со смежными ей сторонами и диагоналями. Остальные вершины, стороны и диагонали образуют ординарный семиугольник. Среди элементарных многоугольников этого семиугольника 28 треугольников, имеющих общую вершину с исходным семиугольником. Возможные количества углов остальных 22 элементарных многоугольников представлены в приведенной ниже таблице (обоснование этой таблицы см. в разборе решения задачи ММ104):
\begin{tabular}{|l|r|r|r|r|r|} \hline & \multicolumn{5}{|c|}{Число углов}\\ \hline № & 3 & 4 & 5 & 6 & 7 \\ \hline 1. & 3 & 13 & 6 & - & - \\ \hline 2. & 4 & 11 & 7 & - & - \\ \hline 3. & 5 & 10 & 6 & 1 & - \\ \hline 4. & 7 & 7 & 7 & - & 1 \\ \hline \end{tabular}
Диагонали, проведенные из зафиксированной нами восьмой вершины, разрежут некоторые из частей разбиения. Однако, при разрезании треугольной части обязательно вновь возникнет треугольник, а разрезании пяти(или более)угольной части возникнет хотя один элементарный многоугольник, имеющий не менее 5 сторон. Поэтому среди 51 части в разбиении восьмиугольника, возникающего на пересечении коротких (соединяющих вершины через одну) диагоналей исходного, будет не менее 3 треугольников и не менее 6 элементарных многоугольников, имеющих боле четырех сторон.
Окончательно получаем, что в разбиении ординарного восьмиугольника участвует не менее 43 треугольников. Из 48 оставшихся многоугольников не менее 6 имеют более четырех сторон.

Обсуждение

Оценки (не менее 43 треугольников и не менее 6 элементарных многоугольников с числом сторон более четырех), вполне достаточны для решения данной задачи, но, скорее всего, занижены.

Участники конкурса привели еще несколько примеров девятиугольников, у которых среди частей разбиения больше четырехугольников, чем треугольников. Анатолий Казмерчук нашел девятиугольник, в разбиении которого участвуют 66 треугольников и 71 четырехугольник, а Андрей Халявин обнаружил девятиугольник, у которого всего 64 элементарных треугольника и целых 75 элементарных четырехугольников.

В преамбуле к задаче я рекомендовал, приступая к ее решению, познакомиться с разбором задачи ММ57. Но сам же пренебрег этим советом. Мне казалось, что в ММ57 обоснованы все возможные варианты разбиения ординарнрго семиугольника. Знание этих вариантов значительно упрощает решение ММ101. Поэтому первоначально данная задача была оценена всего в 5 баллов.

Награды

За правильное решение задачи №101 Андрей Халявин получает 9 призовых баллов (1 балл добавлен за оперативность реакции), а Анатолий Казмерчук - 8 баллов. Кирилл Веденский получает 2 призовых балла, а Николай Дерюгин - 1.

Эстетическая оценка задачи - 5 баллов

===============

Баллы, полученные за решение данной задачи учитываются дважды: в основном Марафоне и в тематическом конкурсе. А сама задача тесно связана с задачами ММ57, ММ101 и ММ104.

ММ102 (КГ-2) (9 баллов)

На какое наименьшее число частей может разбиваться диагоналями выпуклый n-угольник
при:
a) n = 6;
b) n = 7;
c) n = 8;
d) n = 9?

Примечание:
Цена задачи указана весьма условно.
Я умею строго обосновывать минимальность известных мне разбиений не для всех указанных n. Cоответственно и сами известные мне ответы могут оказаться неверными. 9 призовых баллов будет присуждаться за решения аналогичные моему (имеющие тот же ответ и ту же степень строгости его обоснования). За улучшение известных мне ответов, получение более строгих обоснований, получение
(хотя бы частично) обоснованных ответов для бОльших n будут начисляться дополнительные призовые баллы.

Решение

Будем называть диагонали, соединяющие вершины выпуклого многоугольника через одну "короткими"), через две - "средними", через три - "длинными". Точку внутри многоугольника будем называть особенностью порядка $k$, если в ней пересекаются $k+2$ диагоналей. Ясно, что особые точки могут возникать только при пересечении средних и длинных диагоналей.

Ординарный n-угольник разбивается своими диагоналями на $\frac{(n-1)(n-2)(n^2-3n+12)}2$ частей, что при интересующих нас n составляет 25, 50, 91 и 154 соответственно. Каждая особенность порядка k уменьшает количество частей разбиения на $\frac{k(k+1)}2$. Сумму этих чисел по всем особенностям будем называть дефектом многоугольника. Для решения задачи нужно найти максимальный дефект для каждого из данных n.

a) У шестиугольника всего 3 диагонали, не являющихся короткими. Поэтому в шестиугольнике может возникнуть всего одна особенность порядка 1 (она есть, например, в правильном шестиугольнике). Соответственно максимальный возможный дефект шестиугольника - 1 и минимально возможное число частей разбиения - 24.

b) У семиугольника не может быть особенностей, порядок которых больше 1, (вершин не хватает). А то, что число особенностей первого порядка не может превышать 3, следует из рассуждений, приведенных в решении задачи ММ104. В то же время 3 особых точки возможны. На рисунке 1 приведены два способа получения семиугольника с тремя особыми точками: достроением правильного пятиугольника; удалением вершины
правильного восьмиугольника. Разумеется, существуют и подходящие семиугольники никак не связанные с правильными многоугольниками. Итак, максимальный дефект семиугольника - 3, наименьшее возможное число частей разбиения - 47.


c) Представляется очевидным, что максимальный возможный дефект восьмиугольника возникает (в частности) у правильного восьмиугольника. Докажем это утверждение. При наличии особенности второго порядка на средней диагонали не может быть больше двух особенностей. Это легко увидеть на рисунке 2.


На средней диагонали 1-4 уже есть две особенности Y и V. Точки пересечения нашей диагонали с короткими диагоналями не могут быть особенными. Остаются два кандидата на особые точки. Это X и U. Cделать точку X особой можно за счет смещения диагонали 3-8. Но это неизбежно приведет к тому, что точка Y, а заодно и Z перестанут особыми. Аналогично обстоят дела с точкой V. Поэтому на средней диагонали восьмиугольника не может быть больше двух особых точек. Но
у правильного восьмиугольника на каждой средней диагонали их ровно по две. Единственная особенность второго порядка может возникать только на пересечении всех длинных диагоналей восьмиугольника. И у правильного восьмиугольника такая особенность есть.
Таким образом, правильный восьмиугольник обладает максимальным дефектом среди всех восьмиугольников: он имеет 8 особых точек первого порядка и одну особую точку второго порядка. Поэтому дефект правильного восьмиугольника - 11, а число частей разбиения 80.

d) Именно к этому пункту относилось примечание к условию. Мне удалось найти девятигольник с дефектом 17. Я полагаю, что это максимальный возможный дефект, но доказывать это не умею.
Как и все конкурсанты, бравшиеся за задачу ММ102, я стартовал с правильного восьмиугольника. Поместим вершины правильного восьмиугольника на единичной окружности, в точках с координатами $(\cos i\frac \pi 4; sin i\frac \pi 4)$, где $i\in \{0,1,\dots,7\}$. В качестве девятой вершины возьмем точку с координатами $(\frac{-4-\sqrt 2}6; \frac{4-\sqrt 2}6)$ (она тоже лежит на
единичной окружности). Не сложно убедиться, что жирные синие точки на рисунке 3 являются особыми, а две наиболее крупные из них - особенности второго порядка.


Поэтому дефект нашего девятиугольника равен 17, а число частей разбиения - 137.


Обсуждение

Представляется правдоподобной гипотеза: при четных n максимальный дефект имеют правильные n-угольники. Другое утверждение "правильные n-угольники с нечетным числом сторон ординарны" относительно недавно перекочевало из разряда правдоподобных предположений в категорию теорем. Набросок доказательства появился еще в 1936 году в статье G.Bol: Beantwoording van prijsvraag no.17,
Nieuw Archief voor WisKunde 18 (1936), p.14-66. Но строгое доказательство было опубликовано лишь в 1998 году: см. "The number of intersection points made by the diagonals of a regular polygon", B. Poonen, M. Rubinstein, SIAM J. on Discrete Mathematics, Vol. 11, No. 1 (1998), p. 135-156.
В этой статье выведена формула для количества частей разбиения правильного n-угольника при любом n. Оказывается, за исключением центра, никакая особенность правильного n-угольника не может иметь порядок выше 5, а особенности пятого порядка (отличные от центра) впервые встречается в правильном 30-угольнике. В целом же формула для числа частей разбиения распадается на 2520 случаев (которые авторам не без изящества удалось запихнуть в одну не слишком громоздкую формулу).

Если принять гипотезу о том, что правильный десятиугольник - "наиболее дефективный" среди десятиугольников, можно получить еще одно косвенное подтверждение тому, что построенный нами девятиугольник имеет максимальный возможный дефект. Добавив к нашему девятиугольнику вершину, cимметричную девятой вершине относительно центра исходного восьмиугольника (см. рис. 4),
получим десятиугольник с дефектом 26, т.е. с таким же дефектом. как у правильного десятиугольника.


Андрей Халявин нашел для дефекта девятиугольника некоторую оценку сверку. Но она безусловно сильно завышена (28).

Анатолий Казмерчук тоже нашел было девятиугольник с дефектом 17, но при ближайшем рассмотрении этот объект оказался то ли не совсем выпуклым, то ли не совсем девятиугольником (см. рис. 5).


Награды

Андрей Халявин и Анатолий Казмерчук (нашедшие девятиугольники с дефеком 15) получают по 8 призовых баллов. Николай Дерюгин нарисовал девятиугольник разрезаный 137 частей и поразительно похожий на тот, что приведен на рисунке 3 (только красиво раскрашенный), но не снабдил свою картинку обоснованиями (более строгими чем "похоже, что..."). Кроме того, он не обосновал максимальность дефекта правильного восьмиугольника. Николай получает 6 призовых баллов.

Эстетическая оценка задачи - 5 баллов

================

Баллы, полученные за решение данной задачи учитываются дважды: в основном Марафоне и в тематическом конкурсе. А сама задача является прямым продолжением задач ММ57, ММ101 и ММ102.

ММ103 (КГ-3) (3 балла)

Сопоставим каждому выпуклому многоугольнику (сопровождающий) граф по следующему правилу:
вершинами графа будут элементарные многоугольники;
две вершины смежны, если соответствующие многоугольники имеют общую сторону.

1. Доказать, что сопровождающий граф любого выпуклого многоугольника является планарным и двудольным.
2. Сформулировать условие ординарности многоугольника в терминах сопровождающего графа.

Решение

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

Двудольность сопровождающего графа легко доказать по индукции. Проведем сначала одну диагональ. Исходный многоугольник разобьется на два, которые можно выкрасить в разные цвета. Остается заметить, что добавление диагонали не лишает нас возможности правильно (чтобы смежные многоугольники были окрашены в разные цвета) раскрасить многоугольники разбиения в два цвета. Для этого достаточно инвертировать цвета всех многоугольников разбиения по одну сторону од добавляемой диагонали.

Награды

Эстетическая оценка задачи - 4 балла

================

Баллы, полученные за решение данной задачи учитываются дважды: в основном Марафоне и в тематическом конкурсе. А сама задача является прямым продолжением задач ММ57, ММ101, ММ102 и ММ103.

ММ104 (КГ-4) (9 баллов)

Два ординарных n-угольника назовем изоморфными, если изоморфны их сопровождающие графы (см. ММ103).

Два ординарных n-угольника назовем однотипными, если в разбиениях этих многоугольников на элементарные присутствует поровну треугольников, поровну четырехугольников и т.д.

1. Имеется ли логическая зависимость между однотипностью и изоморфностью ординарных многоугольников?
2. На сколько классов однотипных семиугольников разбиваются ординарные семиугольники?
3. На сколько классов изоморфных семиугольников разбиваются ординарные семиугольники?

Решение

1. Очевидно, что и однотипность и изоморфность являются отношениями эквивалентности на множестве ординарных n-угольников. Степень каждой вершины сопровождающего графа равна количеству сторон соответствующего элементарного многоугольника (исключение составляют n элементарных треугольников, у которых одна из сторон является стороной исходного n-угольника). Поскольку степени соответствующих вершин изоморфных графов равны, очевидно, что изоморфные многоугольники являются одновременно и однотипными. То, что обратное утверждение не имеет места будет видно из рассмотрения последующих пунктов.

2-3. Диагонали выпуклого семиугольника, соединяющие вершины через одну, будем называть "короткими", а остальные - "длинными". На рисунках короткие диагонали изображены зеленым цветом, а длинные - красным. Короткие диагонали высекают из исходного семиугольника внутренний семиугольник, содержащий 22 элементарных многоугольника (эти элементарные многоугольники, а также точки пересечения длинных диагоналей мы тоже будем называть внутренними). Остальные 28 элементарных многоугольников (будем называть образованную ими часть семиугольника "периферийной") для любого ординарного (и даже для любого выпуклого) семиугольника являются треугольниками. Строение периферийной части одинаково для всех выпуклых семиугольников. Учитывая это, договоримся при изображении сопровождающего графа, рисовать только 22-вершинный подграф, порожденный внутренними элементарными многоугольниками. (В то же время, исходные семиугольники будем рисовать целиком.)

Стартуем с рассмотрения семиугольника, изоморфного (а значит, и однотипного) правильному. Он изображен на рисунке 1, а внутренняя часть его сопровождающего графа - на рисунке 2 (голубым цветом изображены вершины, соответствующие треугольникам; зеленые - четырехугольникам; желтые - пятиугольникам; красная - семиугольнику).




Пронумеруем вершины семиугольника и введем обозначения для точек пересечения длинных диагоналей: А - на пересечении диагоналей 1-4 и 2-6 и т.д. (см. рисунок). Те из внутренних точек, которые являются вершинами элементарного семиугольника, дополнительно будем называть "центральными", а остальные внутренние точки - "окаймляющими".

Деформируя наш семиугольник, мы можем поменять строение сопровождающего графа только за счет изменения взаимного расположения внутренних точек. Например, смещая вершины 3 и/или 7, можно добиться, чтобы диагональ 3-7 оказалась по другую сторону от точки A. Аналогичного эффекта можно добиться для других окаймляющих точек. Но некоторые такие "перетаскивания" несовместимы. Если мы перетаскиваем соответствующую диагональ за одну из окаймляющих точек, то мы не можем проделать то же самое с соседними окаймляющими точками. Так, перетаскивая диагональ 3-7 за точку A, мы лишаем себя возможности, перетащить диагональ 1-4 за точку B и диагональ 2-6 за точку G. Поэтому элементарный семиугольник можно лишить не более чем трех вершин.

Учитывая вышеизложенное мы легко можем перечислить все классы изоморфных ординарных семиугольников.

1. Семиугольники, изоморфные правильному. Такой семиугольник и центральную часть его сопровождающего графа мы уже рассмотрели (рис. 1-2). У таких семиугольников разбиение состоит из 28+7 треугольников, 7 четырехугольников, 7 пятиугольников и одного семиугольника.

2. Семиугольники полученные из семиугольников первого класса перетаскиванием одной (из соображений симметрии все равно какой) длинной диагонали за окаймляющую точку. На рисунке 3 приведен семиугольник, полученный из первого, перетаскиванием диагонали 2-5 за точку C, а на рисунке 4 - центральная часть его графа. У таких семиугольников разбиение состоит из 28+5 треугольников, 10 четырехугольников, 6 пятиугольников и одного шестиугольника.




3. Семиугольники полученные из семиугольников первого класса перетаскиванием двух диагоналей за окаймляющие точки, расположенные через одну. На рисунке 5 приведен семиугольник, полученный из первого, перетаскиванием диагонали 2-5 за точку C и диагонали 3-7 за точку A. На рисунке 6 приведена внутренняя часть сопровождающего графа. У таких семиугольников разбиение состоит из 28+4 треугольников, 11 четырехугольников и 7 пятиугольников.




4. Семиугольники полученные из семиугольников первого класса перетаскиванием двух диагоналей за окаймляющие точки, расположенные через две. На рисунке 7 приведен семиугольник, полученный из первого, перетаскиванием диагонали 2-5 за точку C и диагонали 2-6 за точку G. На рисунке 6 приведена внутренняя часть сопровождающего графа. У таких семиугольников разбиение состоит из 28+3 треугольников, 13 четырехугольников и 6 пятиугольников.




5. Семиугольники полученные из семиугольников первого класса перетаскиванием трех диагоналей за окаймляющие точки. На рисунке 9 приведен семиугольник, полученный из первого, перетаскиванием диагонали 2-5 за точку C, диагонали 3-7 за точку A и диагонали 4-7 за точку Е. Внутренняя часть сопровождающего графа приведена на рисунке 10. У таких семиугольников разбиение состоит из 28+3 треугольников, 13 четырехугольников и 6 пятиугольников.




Семиугольники из последних двух классов оказались однотипными. В то же время, их сопровождающие графы, очевидно, не изоморфны (например, у одного из них во внутренней части есть вершины степени 3, удаленные друг от друга на 2, а у другого - нет). Таким образом, имеется 5 классов изоморфных и 4 класса однотипных ординарных семиугольников.

Обсуждение

Аналогичная классификация ординарных (или любых выпуклых) n-угольников для бОльших представляется весьма трудной (хотя, по крайней мере, при $n=8$ вполне посильной) задачей.

Награды

За правильное решение этой задачи Анатолий Казмерчук получает 9 призовых баллов.

Эстетическая оценка задачи - 5 баллов

================

[VAL]

Текущее положение конкурсантов
в 11-м туре Математического марафона
и в тематическом конкурсе по комбинаторной геометрии
$\begin{tabular}{|l|l|r|r|r|r|r|} \hline №& Участники& 101 & 102 & 103 & 104 & \Sigma \\ \hline 1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 28 \\ \hline 2.& Андрей Халявин & 9 & 8 & - & - & 17 \\ \hline 3. & Николай Дерюгин & 1 & 6 & - & - & 7 \\ \hline 4. & Кирилл Веденский & 2 & - & 3 & - & 5 \\ \hline 5. & Виктор Филимоненков & - & - & 3 & - & 3 \\ \hline \end{tabular}$

[VAL]

===============

ММ105 (6 баллов)

Математик C загадал некий граф и сообщил математику A степени всех вершин, а математику B - количество вершин и число связных компонент этого графа. Дальше, как водится, состоялся обмен мнениями.

A: Знание степеней всех вершин графа не позволяет мне одозначно определить, какой граф был загадан.

B: Зато я теперь в состоянии сделать это.

Сколько ребер было в загаданном графе?

Примечание:
Рассматриваются классические графы (неориентированные, без петель и кратных ребер).

================

Решение

Приведу (немного подредактированное) решение Виктора Филимоненкова.

Пусть k - число компонент связности графа, n - число вершин, сообщенные В, а m - искомое число ребер. Напомню, что в любом графе справедливо соотношение $n-k \le m \le C_{n-k+1}^2$ (*). Напомню, также, что $K_n$ - это полный n-вершинный граф.

1. $n-k < 4$. Действительно, иначе одна из компонент связности может содержать 5 вершин. Среди связных пятивершинных графов есть два неизоморфных графа с одним набором степеней вершин, это 1, 2, 2, 2, 3 (цикл длины 4 с "хвостом" длины 1 и цикл длины 3 с "хвостом" длины 2). Значит, В в этом случае не может исключить, что одна из компонент связности - один из таких пятивершинных графов, и его знаний количеств вершин и компонент связности не хватит для того, чтобы определить, какая именно эта компонента связности.

2. Коротким простым перебором легко убедиться, что при $n-k < 3$ граф однозначно восстанавливается по степеням вершин.

3. При $n-k = 3$ на основании (*) возможны следующие наборы ненулелвых степеней вершин (кроме них, в графе может присутствовать произвольное количество изолированных вершин):
1) 1,1,1,1,1,1 - 1 граф;
2) 1,1,1,1,2 - 1 граф;
3) 1,1,2,2,2 - 2 графа (3.a граф с компонентами $K_3$ и $K_2$, 3.б - цепь);
4) 1,1,1,3 - 1 граф;
5) 1,1,2,2 - 1 граф;
6) 1,2,2,3 - 1 граф;
7) 2,2,2,2 - 1 граф;
8) 2,2,3,3 - 1 граф;
9) 3,3,3,3 - 1 граф.
Таким образом, только в случае 3 A имел право на свою реплику. Отметим, что граф из пункта граф 3.б соответствует соотношению $n-k = 4$, а этом случае, как было показано, B не может однозначно определить заганный граф. Поэтому был загадан граф из пункта 3.a, имеющий (как, впрочем, и граф из 3.б) 4 ребра.

Ответ: 4 ребра.

Обсуждение

Отмечу, что условие задачи не позволяет однозначно восстановить загаданный граф.
Ведь, кроме компонент $K_3$ и $K_2$, в графе может содержаться несколько компонент $K_1$.

Награды

За правильное решение задачи ММ105 Виктор Филимоненков, Кирилл Веденский и Анатолий Казмерчук получают по 6 призовых баллов, а Николай Дерюгин (почему-то сразу же положивший n = 5) - 3 балла.

Эстетическая оценка задачи - 4.3 балла

===============

Текущее положение конкурсантов
в 11-м туре Математического марафона

$\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& 101 & 102 & 103 & 104 & 105 & \Sigma \\ \hline 1.& Анатолий Казмерчук & 8 & 8 & 3 & 9 & 6 & 34 \\ \hline 2.& Андрей Халявин & 9 & 8 & - & - & - & 17 \\ \hline 3. & Кирилл Веденский & 2 & - & 3 & - & 6 & 11 \\ \hline 4. & Николай Дерюгин & 1 & 6 & - & - & 3 & 10 \\ \hline 5. & Виктор Филимоненков & - & - & 3 & - & 6 & 9 \\ \hline \end{tabular}$

[VAL]

===============

Некоторые из марафонских задач привели к появлению новых последовательностей в OEIS. Макс Алексеев предложил использовать обратный механизм.

ММ106 (от 3 баллов)

Последовательность A116983 из OEIS определяется так:
a(n) есть порядковый номер n! при лексико-графическом упорядочении наборов цифр числа n! (система счисления десятичная). Последнее число, представленное в OEIS, - a(14). Требуется найти еще несколько членов A116983.

Примечание:
Три балла будут присуждаются за нахождение a(15). За нахождение большего числа членов последовательности можно заработать больше баллов (но шкала, конечно, не линейная).

Решение

Приведу решение Кирилла Веденского.

Алгоритм выглядит достаточно простым: посчитаем количество перестановок, следующих до данной.
Для этого суммируем количество перестановок:
- в которых первая цифра меньше исходной;
- в которых первая цифра такая же, а вторая цифра меньше исходной;
...
- в которых первые N-2 цифр такие же, а N-1-я цифра меньше исходной;

Проиллюстрируем на примере $8! = 40320$.
Количество перестановок, в которых первая цифра меньше исходной:
4! (первая цифра 0) + 4!/2! (первая цифра 2, есть две цифры 0) + 4!/2 (первая цифра 3, есть две цифры 0)
Количество перестановок, в которых первая цифра такая же, а вторая цифра меньше исходной;
0 (нет таких)
Количество перестановок, в которых первые 2 цифры такие же, а третья цифра меньше исходной;
2! + 2!
Количество перестановок, в которых первые 3 цифры такие же, а четвертая цифра меньше исходной;
1!

Итого 53 перестановки, значит, 8! - 54-я перестановка из всех перестановок цифр {4, 0, 3, 2, 0}.

$15! = 1307674368000$

Расписываем в то же порядке:
$12!/(3!2!2!2!)$
$11!/(3!2!2!2!)$
$0$
$9!/(2!2!2!) + 9!/(3!2!2!) + 9!/(3!2!2!) + 9!/(3!2!)$
$8!/(2!2!) + 8!/(3!2!) + 8!/(3!2!)$
$7!/2! + 7!/3! + 7!/3! + 7!/3!$
$6!/2! + 6!/3!$
$5!/2!$
$4!/2!$
$3!/2!$
$0$
$0$

Итого $a(15) = 10939036.$

Обсуждение

Способ нахождения членов последовательсти A116983 вполне алгоритмичен, чем и воспользовались некоторые участники, написав программки для вычисления членов A116983. Вот список первых 56 элементов последовательности:

a(1) = 1
a(2) = 1
a(3) = 1
a(4) = 1
a(5) = 4
a(6) = 6
a(7) = 11
a(8) = 54
a(9) = 150
a(10) = 648
a(11) = 5013
a(12) = 9849
a(13) = 19345
a(14) = 1060707
a(15) = 10939036
a(16) = 4343045
a(17) = 2498014850
a(18) = 5271260976
a(19) = 78029366100
a(20) = 531495923280
a(21) = 805809810981
a(22) = 1936900666393
a(23) = 28724010464057580
a(24) = 29052364970866225
a(25) = 75805259574286872
a(26) = 7466893805506395652
a(27) = 80374513001512054041
a(28) = 107970218135938755545
a(29) = 470625860768285164823489
a(30) = 1092067058367696093174712
a(31) = 23984179502628809216577528
a(32) = 28431347279097359718381340
a(33) = 5150626025769827081670834298
a(34) = 1383260201138264136247099733688
a(35) = 40096653135679607283637405247475
a(36) = 3027594894915571935964583506118250
a(37) = 82517117748871209433749833265061771
a(38) = 10023949507379486198666370320376
a(39) = 29591831094276619678264441606954339281
a(40) = 46163337982794725066771282077346710635365
a(41) = 167123778203520614156182186766168917610
a(42) = 4272219633615780983161453419886264089692720
a(43) = 3546219319786770869389311505619069504631590
a(44) = 3204643067047695510545225270846590879418010540
a(45) = 301067471734634074167312982076454590413566273570
a(46) = 3478763899948438152773353635560057199222936720
a(47) = 314243141648440488497781888595628832937846875377365
a(48) = 14170607816144726336291784998260829063896134279304644
a(49) = 81202660426509885662918837537639284122923959544881921
a(50) = 13644407265774224299787535849835296136167182364020957
a(51) = 3052207259954845501804716327832959568946835875197382056
a(52) = 177399590232335095419162842190728774132068534221263601977
a(53) = 63105836544205896419818591639582430508711794388085938746998
a(54) = 1806209354593919702746922384504295016188456176805030340137733
a(55) = 308850865213754797767705699091611299087770935471801259228401390
a(56) = 58908915753538772653766821227935807457550571804703650490041199

И это, разумеется тоже не предел! Например, Анатолий Казмерчук добрался до a(1214), Петр Бежик (по его словам: он прислал меньше членов A116983, чем продекларировал) - аж до a(1300).

Отмечу, что по традиции на задачу, которая показалась скучной, как мне, так и участникам Марафона (см. эстетическую оценку), прислано рекордное для тура количество ответов

Награды

За правильное решение задачи ММ106 Виктор Филимоненков получает 3 призовых балла, Николай Дерюгин (он добрался до a(22)) - 4 баклла, Кирилл Веденский (он дошел до a(56)) - 5 баллов, а Анатолий Казмерчук и Петр Бежик (им покорились более 1000 членов последовательности) - по 7 баллов.

Эстетическая оценка задачи - 2.3 балла