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

[VAL]

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

ММ144 (5 баллов)

На поле e4 стоит чёрный король. Первый игрок ставит на любую клетку доски, не находящуюся под боем чёрного короля, белых королей (по одному за ход). Второй игрок делает (правильный) ход чёрным королём. Игра заканчивается, когда у чёрного короля не будет ходов. Каково минимальное количество ходов, за которое первый игрок может достичь цели?

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


Решение

Приведём решение Сергея Половинкина.

Пусть $f$ - минимальное количество ходов, за которое первый игрок может достичь цели при некотором заданном положении черного короля.
На следующих рисунках приведены значения $f$ для квадратных досок для всех начальных положений черного короля.








Можно сделать некоторые выводы (за небольшими исключениями):
1. Для угловых клеток - $f(0)=3$
2. Слои клеток на краях доски (без углов), назовем эти слои первыми - $f(1)=4$
3. Для слоев клеток, соседних с краевыми слоями (пусть это будет второй слой) $f(2)=5$
4. Для третьего слоя $f(3)=6$
5. Для более дальних слоев $f(4)=7$ и $f(5)=7$.
6. Исключения представляют клетки в 1-ом и 2-ом слоях, расположенные в 3-ем слое относительно другого края (поля с1, с2 или а3, b3).
7. Есть еще и не типовые исключения - на досках $3 \times 3$ и $5 \times 5$

Разберем эти результаты подробнее. Понятно, что на краю доски (особенно в углах) проще запатовать короля черных, поэтому при удалении от края значения $f$ возрастают.
С другой стороны, в некоторых случаях, отсутствие возможности белым "зайти с тыла", ограничивает возможности патования, это объясняет п.6.

Рассмотрим соответствующий пример.
Начальное положение черного короля удобно задать в виде нулевого хода черных, а каждый следующий ход с номером - выставление белого короля и ход черного.
Возьмем доску $6 \times 6$ и рассмотрим типовую партию при черном короле на b2:

0. ... Крb2
1. Крd3
Белые играют естественным образом, черным, чтобы сразу не попасть на край доски (где белые выиграют проще и быстрее) приходится играть
1. ... Крb3

И теперь белые отсекают черных снизу, играя
2. Крb1! Крb4
Черные сделали вынужденный ход, хотя следующий свой ход белые бы сделали на любой ход черных
3. Крb6!
Отсекая черных сверху!

У черных осталось всего 4 клетки, своим 4-м ходом белые уменьшат это количество до двух, а 5-м - запатуют черных.

А на доске $5 \times 5$ белые лишены возможности "отсечь" черных сверху на 3-ем ходу, именно поэтому при короле на $b2$ выигрыш белых на досках всех размерностей достигается быстрее, чем на доске $5 \times 5$ !
Там есть еще одна "хитрость", поэтому покажем соответствующую партию.
0. ... Крb2
1. Крd4! Крb3
2. Kpb1 Kpb4
3. Kpb2 Kpa5!


Белые сыграли тоньше на 1-ом ходу, черные делают прекрасный 3-ий ход, два края доски не дают белым возможности выиграть быстрее 6-ти ходов!
Нечто подобное, только попроще, происходит при короле на с1 (а3).

Теперь как выигрывают белые за 6 ходов при короле черных на 3-ей линии.
Пусть черный король стоит $c3$ на доске $8 \times 8$, белые отвечают, например, $Kpe3$

Основной вариант
0. ... Крc3
1. Крe3 Крc4
2. Kpc6 Kpb4
3. Kpb6 Kpb3
4. Kpb1


Как бы теперь ни играли черные, белые патуют их за 2 хода, например:
4. ... Крb4 5. Kpb2 Kpc4 6. Kpa4 $\times$ или 4. ... Крc4 5. Kpa4 Kpc3 6. Kpc5 $\times$
Другие варианты:
1. ... Крc2 2. Kpa2 Kpd1 3. Kpd3 или 1. ... Крb3 2. Kpb1 Kpb4 3. Kpb6 с переходом к основному варианту.
Таким образом можно запатовать короля черных на любом поле 3-ей линии за $6$ ходов, в том числе и при попадании на "неудобные" поля типа $c2$ и $b3$.

Теперь понятно, как проще всего выиграть за $7$ ходов в искомой позиции. При короле на $e4$ можно пойти 1. Крc5 и теперь черный король имеет неутешительный выбор - или пойти на 3-ю линию (где мы выигрываем за 6 ходов как уже показано) или сделать ход 1. ... Крe5 , что еще быстрее проигрывает после 2. Крg5 с простыми вариантами.

На самом деле к выигрышу белых в $7$ ходов ведет множество продолжений, вот они

На этом рисунке показано - за сколько ходов выигрывают белые при соответствующем первом ходе короля.

Обсуждение=================================================
Рассмотрим доски большего размера.
Могут возникнуть 2 гипотезы - 7 ходов хватит для патования короля на доске любого размера или количество ходов будет и дальше расти. На самом деле число $8$ впервые появляется на доске $11 \times 11$


Но дальнейшего роста уже не происходит, за 8 ходов можно запатовать черного короля на бесконечной доске.
Посмотрим, как это происходит на доске $11 \times 11$, черный король расположен на $f6$, белые играют королем на $h6$. Теперь черные должны играть очень точно, сделать серию единственных ходов, чтобы не проиграть быстрее 8 ходов :

С учетом симметрии у черных 3 возможных хода - $e6$, $e5$($e7$) и $f5$($f7$). Но в тогда в случае 0. ... Крf6 1. Kph6 Kpe6 2. Kpc6 и белые выигрывают в 7 ходов по уже показанным образцам, также достаточно 7 ходов и после 0. ... Крf6 1. Kph6 Kpf5 2. Kpd4 .
Таким образом, черные обязаны играть 0. ... Крf6 1. Kph6 Kpe5! . Восклицательный знак означает единственность хода.
Далее возможны следующие варианты
2. Kpd3 Kpd6!
2. Kpc4 Kpd6! 3. Kpb7 Kpe7!
2. Kpc4 Kpd6! 3. Kpe5 Kpc7!
И только в случае этих единственных ходов белым потребуется 8 ходов.
Но самый интересный такой вариант
2. Kpc5 Kpf4!
Теперь на 3. Kpf2 у черных есть 2 допустимых хода - на $e4$ и $g4$, поэтому сильнее
3. Kpg2 Kpe4! , а на 4. Kpe2 уже любой из 3-х возможных ходов черных ведет к выигрышу на 8-ом ходу. Но при этом белые не пускают черного короля к краю доски, т.е. запатовывают его в центре. Белые могли поставить больше проблем на 4-ом ходу, сходив на $e6$ или $g4$, тогда у черных было бы по 2 допустимых хода.

Поскольку в этой партии ни одна сторона не пользовалась краями доски, то можно к 7 приведенным выше пунктам, добавить 8-ой: $f(x)=8$ при $x \geqslant 6$.

Награды=================================================
За правильное решение задачи и развитие темы Сергей Половинкин получает 5+2=7 призовых баллов.
Дмитрий Пашуткин и Анатолий Казмерчук получают 4 балла. Александр Ларин получает 3 балла.

Эстетическая оценка задачи: 5

[VAL]

======= 145 ========

ММ145 (КГ12) (3 балла)

Сколько внешних диагоналей может иметь n-угольгик?

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

Решение

Пусть между двумя соседними вершинами выпуклой оболочки многоугольника расположено $k$ вершин, не входящих в выпуклую оболочку. Тогда соответствующая "впадина" содержит не более $\frac{k(k+1)}2$ внешних диагоналей.
Пусть в одной "впадине" $k_1$ промежуточных вершин, а в другой $k_2$ и $k_1\ge k_2$. "Перебрасывая" одну промежуточную вершину из второй впадины в первую, мы увеличим максимально возможное число внешних диагоналей.
Поэтому наибольшее число внешних диагоналей достигается, когда "впадина" одна и содержит $n-3$ промежуточных вершины (как минимум три вершины принадлежат выпуклой оболочке) и $k=n-3$.
В случае когда все промежуточные и две смежные им вершины образуют ломаную, "выпуклую в обратную сторону", число внешних диагоналей достигает $\frac{(n-2)(n-3)}2$.
Среди многочисленных способов обоснования того, что все промежуточные значения от 0 до $\frac{(n-2)(n-3)}2$ достижимы приведу вариант, предложенный Дмитрием Пашуткиным:



Собственно говоря, все видно из чертежа. Все промежуточные значения можно получить, меняя параметр $k$ и угол наклона стороны $A_kA_{k+1}$.

Обсуждение

Любопытно, что подавляющее большинство участников Марафона в качестве вспомогательного средства для решения данной задачи использовало решение задачи ММ148 (на мой субъективный взгляд, значительно более трудной).
При этом строгость обоснования вспомогательного утверждения была разной. При оценивании решения ММ148 эта разная строгость нашла бы отражение в призовых баллах (цена ММ148 - 8 баллов). Но ММ145 оценивается всего в 3 балла, а решение ММ148 составляет лишь часть решения ММ145. В такой ситуации разница в строгости обоснования утвеждения про внутренние диагонали на итоговую оценку не повлияла.
Как же теперь поступать при оценивании ММ148 пока не знаю...

Награды

За правильное решение задачи ММ145 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Дмитрий Пашуткин, Кирилл Веденский и Александр Ларин получают по 3 призовых балла. Андрей Халявин получает 2 призовых балла.

Эстетическая оценка - 4.6 балла

Разбор задачи ММ145 подготовил Владимир Лецко

[VAL]

======= 146 ========

ММ146 (4 балла)

При каких $D$ существуют графы диаметра $D$, у которых сумма квадратов степеней вершин равна $D^2$?

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

Решение

Сумма степеней вершин, а следовательно и сумма квадратов степеней вершин, любого графа - четна. Поэтому для нечетных D решений нет.
При $D=2$ наименьшее значение суммы квадратов степеней вершин достигается у двухзвенной цепочки и равно 6. Поэтому $D=2$ тоже не годится.
Не подходит и $D=4$. У цепи длины 4 сумма квадратов степеней вершин - 14. Но добавление любой вершины (любых вершин) без изменения диаметра увеличивает минимум на $1+(3^2-2^2)=6$.
Покажем, что для всех четных $D \ge 6$ нужные графы имеются.
Возьмем цепь длины $D$ и будем добавлять к вершинам отличным от концевых висячие вершины: к одной - $D-6$; к одной - 2; к $\frac D2-3$ - по одной.
Сумма степеней вершин полученного графа составит $(D-4)^2+4^2+\left(\frac D2-3\right)\cdot{3^2}+\frac D2 \cdot 2^2+(2+(D-6)+2+\frac{D}2-3)\cdot 1=D^2$.

Обсуждение

Существует много различных способов построения подходящих графов для четных $D \ge 6$. Вариант приведенный в решении предложен Кириллом Веденским и Анатолием Казмерчуком.
Еще один универсальный метод предложен Виктором Филимоненковым: к одной из внутренних вершин вершин цепи длины $D$ прицепим 2 висячие вершины, а к другой - $\frac D2-3$ трехвзенных цикла.
Другие подходы (в том числе и авторский) либо содержат исключения для малых значений $D$, либо варьируются, например, в зависимости от $D \ mod \ 4$.

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

Награды

За правильное решение задачи ММ146 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Дмитрий Пашуткин, Кирилл Веденский и Андрей Халявин получают по 4 призовых балла. Александр Ларин получает 2 призовых балла.

Эстетическая оценка - 4.6 балла

Разбор задачи ММ146 подготовил Владимир Лецко

[VAL]

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

Текущее положение участников
в XV туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& 141 & 142 & 143 & 144 & 145 &146 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 4 & 8 & 7 & 3 & 4 & 29 \\ \hline 2.& Андрей Халявин & 5 & 4 & 7 & - & 3 & 4 & 23 \\ \hline 3.& Дмитрий Пашуткин & - & 4 & 6 & 4 & 3 & 4 & 21 \\ \hline 4.& Анатолий Казмерчук & 3 & 4 & 2 & 4 & 3 & 4 & 20 \\ \hline 5.& Алексей Волошин & 3 & 4 & 4 & - & 3 & 4 & 18 \\ \hline 5.& Александр Ларин & 2 & 4 & 4 & 3 & 3 & 2 & 18 \\ \hline 7.& Виктор Филимоненков & - & 4 & 6 & - & 3 & 4 & 17 \\ \hline 7.& Кирилл Веденский & 1 & 4 & 5 & - & 3 & 4 & 17 \\ \hline 9.& Николай Дерюгин & 3 & 4 & 3 & - & 3 & - & 13 \\ \hline 10.& iPhonograph & 3 & 4 & 4 & - & - & - & 11 \\ \hline 11.& Sirion & 3 & 4 & 3 & - & - & - & 10 \\ \hline 12.& Евгений Гужавин & 3 & 4 & 2 & - & - & - & 9 \\ \hline 13.& Галина Крюкова & - & 4 & - & - & - & - & 4 \\ \hline 13.& Евгений Машеров & - & 4 & - & - & - & - & 4 \\ \hline 13.& Umnik & - & 4 & - & - & - & - & 4 \\ \hline \end{tabular}

[VAL]

======= 147 ========

ММ147 (КГ13) (6 баллов)

Какое наименьшее число внутренних диагоналей может иметь n-угольник, у которого ровно один угол больше развернутого?

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

Решение

Воспользуюсь чертежом Анатолия Казмерчука:



Размеcтив вершину $A_n$ внутри треугольника, образованного стороной $A_sA_{s+1}$ и диагоналями $A_{s-1}A_{s+1}, A_sA_{s+2}$, добьемся максимального для данного $s$ числа диагоналей, не являющихся внутренними.
Ясно, что внутренними будут диагонали $A_sA_n, A_{s-1}A_n$, а также диагонали выпуклых многоугольников, $A_1A_2\dots A_sA_n$ и $A_{s+1}A_{s+2}\dots A_{n-1}A_n$.
Число диагоналей, не являющихся внутренними, будет наибольшим, когда количества вершин от $A_1$ до $A_s$ и от $A_{s+1}$ до $A_{n-1}$ будут равны или максимально близки между собой (произведение целых положительных сомножителей с постоянной суммой максимально, когда сомножители максимально близки между собой).
При нечетных $n$ и $s=\frac{n-1}2$ получим $2\frac{(s+1)(s-2)}2+2=\frac{(n-1)(n-3)}4$.
При четных $n$ и $s=\frac{n}2$ наименьшее число внутренних диагоналей будет $\frac{(s+1)(s+3)}2+\frac{s(s-2)}2+2=\frac{(n-2)^2}4$.

Обсуждение

Тот же ответ можно получить, вычитая из общего число диагоналей исходного многоугольника число диагоналей, не являющихся внутренними.
Например, для нечетного $n$ имеем: $\frac{(n-1)(n-3)}2-\left(\frac{(n-1)^2}4+1\right)=\frac{(n-1)(n-3)}4$.
Замечу, что среди диагоналей, не являющихся внутренними, одна (на рисунке это $A_1A_{n-1}$ обязательно является внешней. Но внешних диагоналей может быть и более одной. Впрочем, на ход решения и ответ это обстоятельство никак не влияет.
Оба ответа можно объединить в один. Например, так: $\frac{n^2-4n+3+((n+1) \ mod \ 2)}4$.

Награды

За правильное решение задачи ММ147 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Николай Дерюгин и Дмитрий Пашуткин получают по 6 призовых баллов. Александр Ларин получает 5, а Кирилл Веденский - 3 призовых балла.

Эстетическая оценка - 4.4 балла

Разбор задачи ММ147 подготовил Владимир Лецко

[VAL]

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

Текущее положение участников в XV туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& 141 & 142 & 143 & 144 & 145 &146 &147 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 4 & 8 & 7 & 3 & 4 & 6 & 35 \\ \hline 2.& Дмитрий Пашуткин & - & 4 & 6 & 4 & 3 & 4 & 6 & 27 \\ \hline 3.& Анатолий Казмерчук & 3 & 4 & 2 & 4 & 3 & 4 & 6 & 26 \\ \hline 4.& Алексей Волошин & 3 & 4 & 4 & - & 3 & 4 & 6 & 24 \\ \hline 5.& Андрей Халявин & 5 & 4 & 7 & - & 3 & 4 & - & 23 \\ \hline 5.& Александр Ларин & 2 & 4 & 4 & 3 & 3 & 2 & 5 & 23 \\ \hline 5.& Виктор Филимоненков & - & 4 & 6 & - & 3 & 4 & 6 & 23 \\ \hline 8.& Кирилл Веденский & 1 & 4 & 5 & - & 3 & 4 & 3 & 20 \\ \hline 9.& Николай Дерюгин & 3 & 4 & 3 & - & 3 & - & 6 & 19 \\ \hline 10.& iPhonograph & 3 & 4 & 4 & - & - & - & - & 11 \\ \hline 11.& Sirion & 3 & 4 & 3 & - & - & - & - & 10 \\ \hline 12.& Евгений Гужавин & 3 & 4 & 2 & - & - & - & - & 9 \\ \hline 13.& Галина Крюкова & - & 4 & - & - & - & - & - & 4 \\ \hline 13.& Евгений Машеров & - & 4 & - & - & - & - & - & 4 \\ \hline 13.& Umnik & - & 4 & - & - & - & - & - & 4 \\ \hline \end{tabular}

-- 08 окт 2011, 15:29 --

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

Текущее положение участников в тематическом конкурсе
XV тура Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& КГ11 & КГ12 & КГ13 & \Sigma \\ \hline 1.& Сергей Половинкин & 8 & 3 & 6 & 17 \\ \hline 2.& Дмитрий Пашуткин & 6 & 3 & 6 & 15 \\ \hline 2.& Виктор Филимоненков & 6 & 3 & 6 & 15 \\ \hline 4.& Алексей Волошин & 4 & 3 & 6 & 13 \\ \hline 5.& Александр Ларин & 4 & 3 & 5 & 12 \\ \hline 5.& Николай Дерюгин & 3 & 3 & 6 & 12 \\ \hline 7.& Кирилл Веденский & 5 & 3 & 3 & 11 \\ \hline 7.& Анатолий Казмерчук & 2 & 3 & 6 & 11 \\ \hline 9.& Андрей Халявин & 7 & 3 & - & 10 \\ \hline 10.& iPhonograph & 4 & - & - & 4 \\ \hline 11.& Sirion & 3 & - & - & 3 \\ \hline 12.& Евгений Гужавин & 2 & - & - & 2 \\ \hline \end{tabular}

[VAL]

======= 148 ========

ММ148 (8 баллов)

Сколько внутренних диагоналей может иметь n-угольник?

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

Решение

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

Решение: Сначала по индукции докажем, что у любого n-угольника существует по крайней мере n-3 внутренние диагонали.
Для треугольника это утверждение очевидно.
Пусть утверждение выполнено для любого k, меньшего n. Докажем, что тогда оно верно и для n.

Лемма. У любого n-угольника есть хотя бы одна внутренняя диагональ.
Ясно, что у n-угольника есть угол, меньше развернутого. Действительно, проведем прямую, проходящую вне многоугольника, и будем сдвигать ее в сторону многоугольника. Угол при вершине А, которой прямая коснется первой, будет меньше развернутого.
Рассмотрим две соседние с А вершины В и С. Если диагональ ВС внутренняя, то мы доказали лемму. Если ВС не внутренняя, то она пересекает стороны n-угольника, и внутри треугольника АВС есть вершины треугольника. Возьмем луч АВ и начнем его поворачивать к стороне АС. Пусть Д - первая вершина n-угольника, лежащая внутри АВС. Тогда АД - искомая внутренняя диагональ n-угольника.

Вернемся к доказательству базы индукции. Проведем внутреннюю диагональ в n-угольнике. Она разобьет n-угольник на $k_1$-угольник и $k_2$-угольник, где $k_1+k_2=n+2$ (так как 2 вершины у многоугольников разбиения общие, а остальные вершины n-угольника являются вершинами ровно одного из многоугольников разбиения). Значит, по предположению индукции, всего в n-угольнике, считая диагональ разбиения, не меньше, чем $(k_1-3)+(k_2-3)+1 = n+2-5 = n-3$ внутренние диагонали.

Покажем, что многоугольник с таким числом внутренних диагоналей существует.
Действительно, рассмотрим окружность с центром О и точку А вне нее. Проведем из А два касательных отрезка к окружности, Пусть В и С - точки касания. Разобьем дугу ВС на n-3 части, и проведем хорды, стягивающие полученные дужки. В полученном n-угольнике внутренними являются только n-3 диагонали, выходящие из вершины А.



Покажем теперь, что количество внутренних диагоналей может быть и любым, большим чем $n-3$, вплоть до $\frac{n(n-3)}2$ - общего числа диагоналей в n-угольнике. Для этого в многоугольнике, построенном в прошлом абзаце, начнем сдвигать вершины, лежащие между В и С, по лучам, выходящим из А, в сторону дуги окружности ВОС, пока не получим выпуклый многоугольник. Диагонали, выходящие из А, при этом остаются внутренними. Будем добиваться того, чтобы ни в какой момент времени не было одновременно больше одной тройки вершин, лежащих на одной прямой (при необходимости чуть "притормаживая" тот момент, когда или "ускоряя" какие-то вершины). Это гарантирует, что количество внутренних диагоналей не будет меняться более, чем 1. Так как в конце движения таких диагоналей становится n(n-3)/2, а в начале движения (n-3), то в процессе движения возникали многоугольники с любым количеством внутренних диагоналей от между этими двумя числами.

Ответ: любое целое число от $n-3$ до $\frac{n(n-3)}2$

Обсуждение

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





Но одну особенность n-3,n-угольники, имеющие ровно n-3 внутренних диагонали, все же имеют:
Из приведенного в решении доказательства легко выводится такое утверждение: количество внутренних диагоналей n-угольника равно n-3 тогда и только тогда, когда никакие две из них не пересекаются внутри треугольника.
Иными словами, такие многоугольники имеют единственную триангуляцию диагоналями на n-2 треугольника.

При решении данной задачи очень ярко проявились разночтения в понимании разными людьми очевидности в математике.
С моей (безусловно субъективной) точки зрения, наличие и любого многоугольника хотя бы одной внутренней диагонали и, тем более, триангуляции совсем не очевидна. В то же время, достижимость всех промежуточных случаев от $n-3$ до $\frac{n(n-3)}2$ внутренних при некоторой деформации n-угольника, имеющего ровно n-3 внутренних диагонали, в выпуклый, представляется мне вполне очевидной.
Некоторые участники марафона наоборот посчитали очевидным наличие триангуляции и все внимание сосредоточили на (гораздо более подробном, чем приведенное) доказательстве достижимости промежуточных случаев.
Были и те, кому было не очевидно ни первое, ни второе. А также те, кому наоборот все было очевидно.

Награды

За правильное решение задачи ММ148 Анатолий Казмерчук, Виктор Филимоненков, Сергей Половинкин и Дмитрий Пашуткин получают по 8 призовых баллов. Алексей Волошин, получает 7, а Александр Ларин - 6 призовых баллов.

Эстетическая оценка - 4.4 балла

Разбор задачи ММ148 подготовил Владимир Лецко

-- 16 окт 2011, 17:56 --

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

Текущее положение участников в XV туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 141 & 142 & 143 & 144 & 145 &146 &147 & 148 &\Sigma \\ \hline 1.& Сергей Половинкин & 3 & 4 & 8 & 7 & 3 & 4 & 6 & 8 & 43 \\ \hline 2.& Дмитрий Пашуткин & - & 4 & 6 & 4 & 3 & 4 & 6 & 8 & 35 \\ \hline 3.& Анатолий Казмерчук & 3 & 4 & 2 & 4 & 3 & 4 & 6 & 8 & 34 \\ \hline 4.& Алексей Волошин & 3 & 4 & 4 & - & 3 & 4 & 6 & 7 & 31 \\ \hline 5.& Виктор Филимоненков & - & 4 & 6 & - & 3 & 4 & 6 & 8 & 31 \\ \hline 6.& Александр Ларин & 2 & 4 & 4 & 3 & 3 & 2 & 5 & 6 & 29 \\ \hline 7.& Андрей Халявин & 5 & 4 & 7 & - & 3 & 4 & - & - & 23 \\ \hline 8.& Кирилл Веденский & 1 & 4 & 5 & - & 3 & 4 & 3 & - & 20 \\ \hline 9.& Николай Дерюгин & 3 & 4 & 3 & - & 3 & - & 6 & - & 19 \\ \hline 10.& iPhonograph & 3 & 4 & 4 & - & - & - & - & - & 11 \\ \hline 11.& Sirion & 3 & 4 & 3 & - & - & - & - & - & 10 \\ \hline 12.& Евгений Гужавин & 3 & 4 & 2 & - & - & - & - & - & 9 \\ \hline 13.& Галина Крюкова & - & 4 & - & - & - & - & - & - & 4 \\ \hline 13.& Евгений Машеров & - & 4 & - & - & - & - & - & - & 4 \\ \hline 13.& Umnik & - & 4 & - & - & - & - & - & - & 4 \\ \hline \end{tabular}

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

Текущее положение участников в тематическом конкурсе
XV тура Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& КГ11 & КГ12 & КГ13 & КГ14 &\Sigma \\ \hline 1.& Сергей Половинкин & 8 & 3 & 6 & 8 & 25 \\ \hline 2.& Дмитрий Пашуткин & 6 & 3 & 6 & 8 & 23 \\ \hline 2.& Виктор Филимоненков & 6 & 3 & 6 & 8 & 23 \\ \hline 4.& Алексей Волошин & 4 & 3 & 6 & 7 & 20 \\ \hline 5.& Анатолий Казмерчук & 2 & 3 & 6 & 8 & 19 \\ \hline 6.& Александр Ларин & 4 & 3 & 5 & 6 & 18 \\ \hline 7.& Николай Дерюгин & 3 & 3 & 6 & - & 12 \\ \hline 8.& Кирилл Веденский & 5 & 3 & 3 & - & 11 \\ \hline 9.& Андрей Халявин & 7 & 3 & - & - & 10 \\ \hline 10.& iPhonograph & 4 & - & - & - & 4 \\ \hline 11.& Sirion & 3 & - & - & - & 3 \\ \hline 12.& Евгений Гужавин & 2 & - & - & - & 2 \\ \hline \end{tabular}

[VAL]

======= 149 ========

ММ149 (8 баллов)

При каком наименьшем $n$ в группе перестановок $S_n$ существует подгруппа порядка 253? Привести пример такой подгруппы.

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

Решение

Приведу решение Андрея Халявина, замечательное своей краткостью.
$253=23\cdot 11$. Поэтому по теореме Силова в подгруппе должен быть элемент порядка 23. Значит, $n\ge 23$.
Пусть $g$ - первообразный корень по модулю 23. Тогда подгруппа группы $S_{23}$, состоящая из перестановок $x\longrightarrow g^{2s}x+t \mod 23, \ 0\le s<11, \ 0\le t<23$, имеет порядок 253.
Ответ: $n=23$

Обсуждение

Приведу более лобовой (если хотите, более тупой) способ построения требуемой подгруппы группы $S_{23}$.
Возьмем цикл $a=(1 \ 2 \ 3 \dots \ 22 \ 23)$ и будем строить перестановку $b$ такую, что $bab^{-1}=a^2$.
Заметим, что $a^2=(1 \ 3 \ 5 \ 7 \ 9 \ 11 \ 13 \ 15 \ 17 \ 19 \ 21 \ 23 \ 2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20 \ 22)$.
Пусть $b(1)=2$. Тогда при $bab^{-1}$ имеем: $1\longrightarrow 2\longrightarrow 3 \longrightarrow 3$. Значит, $b^{-1}(3)=3$ и $b(3)=3$.
Тогда $3\longrightarrow 3\longrightarrow 4 \longrightarrow 5$. Значит, $b^{-1}(4)=5$ и $b(5)=4$.
Тогда $5\longrightarrow 4\longrightarrow 5 \longrightarrow 7$. Значит, $b^{-1}(5)=7$ и $b(7)=5$.
Тогда $7\longrightarrow 5\longrightarrow 6 \longrightarrow 9$. Значит, $b^{-1}(6)=9$ и $b(9)=6$.
Продолжая в том же духе, получим $b=(1 \ 2 \ 14 \ 20 \ 23 \ 13 \ 8 \ 17 \ 10 \ 18 \ 22)(4 \ 15 \ 9 \ 6 \ 16 \ 21 \ 12 \ 19 \ 11 \ 7 \ 5)$.
Непосредственно проверяется, что подгруппа, порожденная $a$ и $b$, имеет порядок 253.

Пусть $p<q$ - простые числа. С помощью теоремы Силова легко доказывается, что, если $q$ не сравнимо с 1 по модулю $p$, то группа порядка $pq$ циклическая. Такая группа может быть реализована перестановками множества, состоящего не менее, чем из $p+q$ элементов.
Если же $q$ сравнимо с 1 по модулю $p$, то обязательно найдется группа порядка $pq$, реализуемая перестановками из $S_q$. Подробности можно найти, например, в книжке М.Каргаполов, Ю.Мерзляков. "Основы теории групп"


Награды

За правильное решение и обобщение задачи ММ149 Алексей Волошин получает 9 призовых баллов. Анатолий Казмерчук, Виктор Филимоненков, Sirion и Андрей Халявин получают по 8 призовых баллов. Сергей Половинкин и Дмитрий Пашуткин (нашедшие нужные подгруппы лишь в $S_{34}$) получают по 2 призовых балла.

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

Разбор задачи ММ149 подготовил Владимир Лецко

-- 23 окт 2011, 11:41 --

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

Текущее положение участников в XV туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 141 & 142 & 143 & 144 & 145 &146 &147 & 148 & 149 &\Sigma \\ \hline 1.& Сергей Половинкин & 3 & 4 & 8 & 7 & 3 & 4 & 6 & 8 & 2 & 45 \\ \hline 2.& Анатолий Казмерчук & 3 & 4 & 2 & 4 & 3 & 4 & 6 & 8 & 8 & 42 \\ \hline 3.& Алексей Волошин & 3 & 4 & 4 & - & 3 & 4 & 6 & 7 & 9 & 40 \\ \hline 4.& Виктор Филимоненков & - & 4 & 6 & - & 3 & 4 & 6 & 8 & 8 & 39 \\ \hline 5.& Дмитрий Пашуткин & - & 4 & 6 & 4 & 3 & 4 & 6 & 8 & 2 & 37 \\ \hline 6.& Андрей Халявин & 5 & 4 & 7 & - & 3 & 4 & - & - & 8 & 31 \\ \hline 7.& Александр Ларин & 2 & 4 & 4 & 3 & 3 & 2 & 5 & 6 & - & 29 \\ \hline 8.& Кирилл Веденский & 1 & 4 & 5 & - & 3 & 4 & 3 & - & - & 20 \\ \hline 9.& Николай Дерюгин & 3 & 4 & 3 & - & 3 & - & 6 & - & - & 19 \\ \hline 10.& Sirion & 3 & 4 & 3 & - & - & - & - & - & 8 & 18 \\ \hline 11.& iPhonograph & 3 & 4 & 4 & - & - & - & - & - & - & 11 \\ \hline 12.& Евгений Гужавин & 3 & 4 & 2 & - & - & - & - & - & - & 9 \\ \hline 13.& Галина Крюкова & - & 4 & - & - & - & - & - & - & - & 4 \\ \hline 13.& Евгений Машеров & - & 4 & - & - & - & - & - & - & - & 4 \\ \hline 13.& Umnik & - & 4 & - & - & - & - & - & - & - & 4 \\ \hline \end{tabular}

[VAL]

======= 150 ========

ММ150 (12 баллов)

Каждому n-угольнику поставим в соответствие ожерелье из n бусин белого, зеленого и красного цветов следующим образом: свободой стороне соответствует белая бусина; полусвободной - зеленая; зажатой - красная.
Два n-угольника назовем эквивалентными, если им соответствуют одинаковые ожерелья (ожерелье не меняется при поворотах и переворачивании). На сколько классов эквивалентности разобьются 20-угольники?

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

Решение

Еще раз приведу решение Андрея Халявина.

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

Подсчитаем количество черно-белых ожерелий без учета ограничения, что черных бусин не менее трех.
Воспользуемся леммой Бернсайда. В качестве группы преобразований $G$ выступает группа диэдра, состоящая из 20-и симметрий и 20-и поворотов (включая тождественный).
Если $g \in G$ - симметрия, ось которой проходит через две бусины, то для $g$ имеется $2^{11}$ неподвижных конфигураций. Если же ось симметрии не проходит через бусины, для $g$ имеется $2^{10}$ неподвижных конфигураций. Значит, вклад симметрий $10\left(2^{11}+2^{10}\right)$.
Для поворотов имеем сумму

$$\frac1{40}\sum_{d|20}\varphi(d)2^{\frac{20}d}.$$

Итого получаем

$$\frac1{40}\left(10\left(2^{11}+2^{10}\right)+2^{20}+2^{10}+2\cdot2^5+4\cdot2^4+4\cdot2^2+8\cdot2\right)=27012.$$

Очевидно, что существует ровно одно ожерелье из белых бусин, одно ожерелье с одной черной бусиной и 10 ожерелий с двумя черными бусинами. Поэтому окончательно получаем $27012-1-1-10=27000$ классов 20-угольников.


Обсуждение

Задача о подсчете числа ожерелий широко известна. Наиболее подробное и доступное изложение (среди известных мне) можно найти в книге Дж. Андерсона "Дискретная математика и комбинаторика".

Разумеется, вместо 20-угольников можно было рассматривать произвольные n-угольники. Число 20 привлекло меня красотой ответа, являющегося в этом случае круглым числом и, к тому же, полным кубом!

С помощью леммы Бернсайнда можно вывести и явную формулу для подсчета ожерелий, в которых число бусин каждого цвета фиксировано. Например, число черно-белых ожерелий из $n$ бусин, среди которых и $m$ черных, подсчитывается по формуле

$$\frac12\left(\frac1n \sum_{d|(n,m)}\varphi(d)C^{m/d}_{n/d}+C^{\lfloor m/2\rfloor}_{\lfloor (n-m)/2\rfloor+\lfloor m/2\rfloor}\right).$$

Вывод этой формулы можно посмотреть, например, здесь.
При $n=20$, суммируя по всем $m \ge3$, вновь получим 27000.

Интересно, что если не различать полусвободные и зажатые стороны, задача станет сложнее.
Пусть свободным сторонам соответствуют белые бусины, а прочим - красные. Если сторона не является свободной, то хотя бы одна из соседних с ней сторон тоже не является свободной. Поэтому красная бусина не может быть окружена белыми. Таким образом, при $n>5$ интересующее нас число классов равно количеству ожерелий, которые можно составить из n белых и красных бусин, при условии, что никакая красная бусина не окружена белыми.
Я посчитал количество классов для всех $n \le 18$ (например, при $n=18$ получается 799 классов), но общей формулы мне вывести не удалось.

В заключение еще об одной классификации, для которой мне не удалось вывести общую формулу для подсчета числа классов.
Будем считать эквивалентными n-угольники, у которых поровну как внутренних, так и внешних диагоналей.
Можно показать, что число классов не превосходит $\frac{n^4-10n^3+39n^2-70n+56}8$. Но, начиная с $n=6$, эта оценка завышена.


Награды

За правильное решение задачи ММ150 Алексей Волошин, Анатолий Казмерчук и Андрей Халявин получают по 12 призовых баллов. Сергей Половинкин получает 11, Виктор Филимоненков - 9 призовых баллов.

Эстетическая оценка - 4.7 балла

Разбор задачи ММ150 подготовил Владимир Лецко

-- 01 ноя 2011, 19:36 --

Итоговое положение участников в тематическом конкурсе
XV тура Математического марафона

\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} \hline №& Участники& КГ11 & КГ12 & КГ13 & КГ14 & КГ15 &\Sigma \\ \hline 1.& Сергей Половинкин & 8 & 3 & 6 & 8 & 11 & 36 \\ \hline 2.& Виктор Филимоненков & 6 & 3 & 6 & 8 & 9 & 32 \\ \hline 2.& Алексей Волошин & 4 & 3 & 6 & 7 & 12 & 32 \\ \hline 4.& Анатолий Казмерчук & 2 & 3 & 6 & 8 & 12 & 31 \\ \hline 5.& Дмитрий Пашуткин & 6 & 3 & 6 & 8 & - & 23 \\ \hline 6.& Андрей Халявин & 7 & 3 & - & - & 12 & 22 \\ \hline 7.& Александр Ларин & 4 & 3 & 5 & 6 & - & 18 \\ \hline 8.& Николай Дерюгин & 3 & 3 & 6 & - & - & 12 \\ \hline 9.& Кирилл Веденский & 5 & 3 & 3 & - & - & 11 \\ \hline 10.& iPhonograph & 4 & - & - & - & - & 4 \\ \hline 11.& Sirion & 3 & - & - & - & - & 3 \\ \hline 12.& Евгений Гужавин & 2 & - & - & - & - & 2 \\ \hline \end{tabular}

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

Итоговое положение участников в XV туре Математического марафона

\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 141 & 142 & 143 & 144 & 145 &146 &147 & 148 & 149 & 150 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 4 & 8 & 7 & 3 & 4 & 6 & 8 & 2 & 11 & 56 \\ \hline 2.& Анатолий Казмерчук & 3 & 4 & 2 & 4 & 3 & 4 & 6 & 8 & 8 & 12 & 54 \\ \hline 3.& Алексей Волошин & 3 & 4 & 4 & - & 3 & 4 & 6 & 7 & 9 & 12 & 52 \\ \hline 4.& Виктор Филимоненков & - & 4 & 6 & - & 3 & 4 & 6 & 8 & 8 & 9 & 48 \\ \hline 5.& Андрей Халявин & 5 & 4 & 7 & - & 3 & 4 & - & - & 8 & 12 & 43 \\ \hline 6.& Дмитрий Пашуткин & - & 4 & 6 & 4 & 3 & 4 & 6 & 8 & 2 & - & 37 \\ \hline 7.& Александр Ларин & 2 & 4 & 4 & 3 & 3 & 2 & 5 & 6 & - & - & 29 \\ \hline 8.& Кирилл Веденский & 1 & 4 & 5 & - & 3 & 4 & 3 & - & - & - & 20 \\ \hline 9.& Николай Дерюгин & 3 & 4 & 3 & - & 3 & - & 6 & - & - & - & 19 \\ \hline 10.& Sirion & 3 & 4 & 3 & - & - & - & - & - & 8 & - & 18 \\ \hline 11.& iPhonograph & 3 & 4 & 4 & - & - & - & - & - & - & - & 11 \\ \hline 12.& Евгений Гужавин & 3 & 4 & 2 & - & - & - & - & - & - & - & 9 \\ \hline 13.& Галина Крюкова & - & 4 & - & - & - & - & - & - & - & - & 4 \\ \hline 13.& Евгений Машеров & - & 4 & - & - & - & - & - & - & - & - & 4 \\ \hline 13.& Umnik & - & 4 & - & - & - & - & - & - & - & - & 4 \\ \hline \end{tabular}

Мои поздравления лауреатам!

В качестве приза победителям предоставляется уникальная возможность - право совершенно бесплатно поучаствовать в 5-м реальном конкурсе (см. соответствующую тему в "Свободном полете") :)

PS: Для остальных марафонцев участие в 5-м реальном конкурсе является почетной обязанностью ;)

[VAL]

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

B общем зачете Марафона произошли серьезные изменения. В XV-м туре Анатолий Казмерчук обошел многолетнего лидера Марафона Владислава Франка и возглавил гонку.

Есть изменения и в стане преследователей. A вот как выглядит первая десятка целиком:

Положение лидирующей группы после 15-и туров Марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|c|} \hline Участники &I-IV&V&VI&VII&VIII&IX&X&XI&XII&XIII&XIV&XV&\Sigma\\ \hline 1. А.Казмерчук &-&-&-&-&55&67&-&61&74&61&45&54&417\\ \hline 2. В.Франк &85&47&85&59&47&23&33&-&6&-&26&-&411\\ \hline 3. В.Филимоненков &-&-&77&64&60&7&21&32&32&22&-&48&363\\ \hline 4. А.Волошин &-&-&-&-&-&-&45&20&72&61&47&52&297\\ \hline 5. О.Полубасов &-&77&-&65&45&81&-&-&-&-&-&-&268\\ \hline 6. С.Половинкин &-&-&-&-&-&-&-&-&80&57&64&56&257\\ \hline 7. Н.Дерюгин &-&-&-&-&-&18&3&30&49&21&20&19&160\\ \hline 8. Д.Пашуткин &-&-&-&-&-&-&-&-&41&16&48&43&148\\ \hline 9. А.Халявин &-&-&-&-&-&-&49&17&6&-&-&43&115\\ \hline 10. А.Богданов &-&45&-&52&15&-&-&-&-&-&-&-& 112\\ \hline \end{tabular}

[VAL]

Поздравляю всех марафонцев и болельщиков с Новогодними праздниками!

Участникам желаю успехов на тернистой марафонской дистанции! Болельщикам желаю поскорее стать участниками! Здоровья, счастья и творческих достижений и радости от них желаю всем!

А вот и новогодний подарок:

XVI тур Математического марафона

[VAL]

Внимание:
В условии ММ157 допущена опечатка. Конечно же, найти надо KL, а не KM.

[VAL]

Со стыдом и прискорбием сообщаю, что обнаружил в условиях задач текущего тура еще одну опечатку. Маленькую, но очень принципиальную:
В условии задачи ММ160 вместо "$g>2$ " должно быть "$g \ge 2$ ".

[VAL]

========= 151 ==========

ММ151 (ТГ-1) (4 балла)

Каждая клетка доски $4\times 4$ покрашена либо в черный, либо в белый цвет.
На множестве клеток задана структура графа. Две клетки смежны, если: они одного цвета; у них поровну соседей каждого цвета. (Соседними считаются клетки имеющие общую сторону.)
Какое наименьшее и наибольшее количество ребер может иметь такой граф, если:
а) количество клеток одного цвета может быть любым;
б) черных и белых клеток поровну?

Решение

Очевидно, что клетки, имеющие разное число соседей, не могут быть смежны. Поэтому в графе не менее трех связных компонент, образованных соответственно: угловыми клетками (их 4); боковыми, но не угловыми (их 8); центральными (их 4).
Поэтому в графе не более чем $2C_4^2+C_8^2 = 40$ ребер. Это число очевидно достигается при такой раскраске:



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



Поскольку на каждой из диаграмм поровну черных и белых клеток, ответы к пунктам a) и b) совпадают: минимальное количество ребер - 0; максимальное - 40.

Обсуждение

Многие участники Марафона не ограничились рассмотрением случаев указанных в условии.
Обобщение задачи велось преимущественно по трем направлениям:
нахождение наибольшего и наименьшего числа ребер в случае фиксированного числа белых клеток (обобщение пункта б);
нахождение всех возможных значений числа ребер;
рассмотрение досок $n\times n$ при других n.
Конечно, можно было бы обобщать задачу и в других направлениях, например, изменив число разрешенных цветов. То таких попыток участники не делали. Воздержусь от них и я
Наибольших успехов в обобщении задачи добился Олег Полубасов.
Приведу найденные им графы с минимальным числом ребер для досок $5\times 5$ и $6\times 6$.





В первом случае граф содержит 4 ребра. Меньше 4-х ребер быть не может. Как уже отмечалось, для боковых клеток имеется всего 8 возможностей, а на доске $5\times 5$ таких клеток 12. Поэтому при разбиении их на классы 4 класса будут двухэлементными (если использовать классы с бОльшим числом элементов число ребер только увеличится).
Во втором случае, граф содержит 14 ребер. Это тоже гарантированный минимум. Боковых клеток для доски $6\times 6$ уже 16, что дает, как минимум 8 ребер. Еще, как минимум, 6 ребер образую центральные клетки. Их тоже 16, а вариантов для них 10 (от нуля до четырех белых соседей и цвет самой клетки).

Максимальное количестве ребер, очевидно, достигается при одноцветной раскраске графа и равно $C_4^2+C_{4n-8}^2+C_{(n-2)^2}^2$. При больших n невозможна ситуация, когда такое же число ребер возникнет при раскраске, в которой представлены оба цвета.

Замечу, что граф, возникающий при каждой раскраске доски $n\times n$, всегда является графом некого отношения эквилентности, заданного на множестве из $n^2$ элементов. По условию задачи каждое такое отношение содержит не менее 3-х и не более 22-х (до 4-х для угловых клеток, до 8-и - для боковых и до 10-и - для центральных) классов. Если использовать большее число цветов, все равно каждая раскраска будет задавать отношение эквивалентности, только возможных классов станет больше.

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

Награды

За правильное решение и ряд интересных обобщений задачи ММ151 Олег Полубасов получает 5 призовых баллов. Сергей Половинкин, Алексей Волошин, Евгений Гужавин, Виктор Филимоненков и Николай Дерюгин получают по 4 призовых балла. (Последний, несмотря на "тождество" $6+6+28=42$. Все же задача на графы, а не на арифметику ). Александр Князев получает 1 призовой балл.

Эстетическая оценка - 4.2 балла

Разбор задачи ММ151 подготовил Владимир Лецко

[VAL]

Про просьбам участников Марафона срок приема решений ММ152 продлен до 13.02.12