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

[VAL]

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

Текущее положение участников
в XII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& 111 & 112 & 113 & 114 & 115 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 12 & 39 \\ \hline 2.& Алексей Волошин & 2 & 6 & 11 & 7 & 11 & 37 \\ \hline 3.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 10 & 36 \\ \hline 4.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 10 & 30 \\ \hline 5.& Николай Дерюгин & 3 & 4 & 9 & 7 & 4 & 27 \\ \hline 6.& Виктор Филимоненков & 2 & 6 & 10 & 7 & & 25 \\ \hline 7.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 10 & 17 \\ \hline 8.& Кирилл Веденский & 0 & 6 & 9 & 0 & & 15 \\ \hline 9.& Илья Гермашев & 0 & 0 & 0 & 7 & & 7 \\ \hline 10.& Андрей Халявин & 0 & 6 & 0 & 0 & & 6 \\ \hline 10.& Владислав Франк & 0 & 6 & 0 & 0 & & 6 \\ \hline 12.& Александр Расстригин & 3 & 0 & 0 & 0 & & 3 \\ \hline 13.& SiO2 & 0 & 0 & 0 & & 1 & 1 \\ \hline \end{tabular}$

[VAL]

Разъяснение
В связи с появившимися вопросами по уточнению условия задачи ММ116, разъясняю, что речь идет о классических графах (никаких петель, кратных ребер и т.п. нет)

[VAL]

Задача ММ116 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Задача ММ116 навеяна обсуждением одной из последовательностей в OEIS.

ММ116 (10 баллов)

Сколько существует связных графов, таких что произведение степеней вершин равно:
а) сумме степеней вершин;
б) сумме квадратов степеней вершин?

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

Решение

а) Приведу решение Юрия Вольвовского (впрочем, решения некоторых других участников, по сути идентичны).

Сначала докажем, что связный граф, у которого произведение степеней вершин не больше их суммы, является деревом.
Доказывается в два шага:
(1) если нет висячих вершин, то произведение равно как минимум $2^n$, а сумма никак не больше $n(n-1)$, что невозможно.
(2) удаляя висячую вершину, мы уменьшаем сумму на 2, а произведение на 1 только в том случае, если граф является звездочкой (т. е. деревом с одной вершиной степени больше 1). В остальных случаях, произведение уменьшается как минимум на 2 и утверждение следует по индукции.
Остается разобраться с деревьями.
Для начала заметим, что одновершинное дерево удовлетворяет условию.
Пусть теперь в дереве есть $k$ вершин степени больше единицы. Произведение их степеней не меньше, чем $(n-k)2^{k-1}$, что должно быть не больше, чем $2n-2$. Это возможно только если $k=2$ или $k=3$.
При $k=3$ имеем $4(n-3) \le 2n-2$, т.е.$n \le 5$. Но в дереве не менее двух висячих вершин, поэтому $n=5$ и граф - цепочка длины 4.
Если $k=2$, то сумма степеней этих двух вершин должна быть равна $n$. Пусть степень одной из двух узловых вершин равна $s$.
Получаем уравнение $s(n-s)=2n-2$. Оно имеет целые решения, только если $n^2 - 8n + 8$ - полный квадрат, что возможно только при $n = 7$. Тогда степени узловых вершин 3 и 4 и мы нашли еще один (и последний) требуемый граф: дерево со степенями вершин $1, 1, 1, 1, 1, 3, 4$.

Ответ к пункту а): 3 графа.

б) Докажем, что множество требуемых графов бесконечно.
Для этого укажем алгоритм построения бесконечной серии подходящих графов.
Легко убедиться, что дерево, у которого 10 вершин являются висячими, а три остальных имеют степени 3, 4, 4, удовлетворяет всем условиям пункта б).
Это дерево (на самом деле таких деревьев 3, но для нас это не важно) будет открывать нашу серию.
Положим $x_0=4, \ y_0 = 4, \ \ x_k = y_{k-1}, \ y_k = 3y_{k-1}-x_{k-1}-1$. Легко убедиться (по индукции), что дерево, у которого три вершины, не являющиеся висячими, имеют степени $3, \ x_k, \ y_k$ при любом натуральном будет удовлетворять условиям пункта б).

Ответ к пункту б): бесконечно много графов.

Обсуждение

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

Очевидно, что построенная нами бесконечная серия графов, не исчерпывает всех графов, удовлетворяющих условиям пункта б).
Каждое дерево с тремя узловыми вершинами, удовлетворяющее условиям пункта б) порождает серию, аналогичную описанной.
Например, стартуя с дерева со степенями узловых вершин $4, 4, 12$ положим $x_0=4, \ y_0 = 12, \ \ x_k = y_{k-1}, \ y_k = 4y_{k-1}-x_{k-1}-1$. Деревья со степенями узловых вершин $(4, x_k, y_k)$ будут обладать требуемыми свойствами.

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

Юрий Вольвовский указал красивый способ получать новые подходящие графы из любого графа, удовлетворяющего условию пункта б), а не только из деревьев с тремя узловыми вершинами:
На любом ребре такого графа возьмем новую вершину (выражаясь аккуратнее, заменим ребро конструкцией ребро-вершина-ребро) и подвесим к ней еще $x-4$ вершины, где $x$ - произведение степеней вершин исходного графа. Тривиально проверяется, что полученный граф будет подходящим.

Награды

За решение задачи ММ116 участникам начислены следующие призовые баллы:
Дмитрий Пашуткин и Юрий Вольвовский - по 10 баллов;
Сергей Половинкин - 9 баллов;
Эдвард Туркевич, Алексей Волошин и Анатолий Казмерчук - по 6 призовых баллов.

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

[VAL]

===============
Задача ММ117 утратила статус конкурсной и может свободно обсуждаться.

Призовые баллы за решение ММ117 учитываются дважды: в тематическом конкурсе и в основном Марафоне.
А сама задача ММ117 является прямым продолжением задачи ММ115 и так же как ММ115 предложена Сергеем Половинкиным.

ММ117 (Ш-4) (7 баллов)

На шахматной доске расставлено 64 белых коня. Какое минимальное количество коней нужно заменить
черными, так чтобы в полученной позиции, действуя по правилам задачи ММ115, было бы невозможно получить хотя бы один одноцветный квадрат 5Х5?
Каково количество таких позиций?

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

Решение

Приведу решение Дмитрия Пашуткина.

Очевидно, что одного чёрного коня недостаточно.
Покажем, что два чёрных коня можно расположить так, чтобы получить одноцветный белый квадрат было нельзя и заодно найдем количество таких размещений чёрных коней.
Сначала заметим, что если чёрные кони (один или оба) стоят на выделенных красным цветом полях, то такой квадрат можно преобразовать к одноцветному.
Для угловых полей это очевидно. Цвет всех полей, кроме центрального, можно поменять на противоположный, если выполнить преобразования по синим линиям на рис. 1:



Разобьём доску на несколько областей (рис. 2):
Рассмотрим варианты расположения 2-х черных коней на доске.
Если оба коня находятся в жёлтой области, то на доске останется белый квадрат 5х5.
Пусть один из чёрных коней стоит на жёлтой области. Не теряя общности, можно считать, что конь стоит в квадрате A1. Покажем, что в этом случае всегда можно построить белый квадрат. Действительно, если второй конь не стоит в области C1, то обязательно останется белый квадрат 5х5. Если же второй конь находится в области C1, то он может располагаться либо в клетках d4,d5,e4 и тогда он будет находиться в угловой клетке белого квадрата 5х5, либо в клетке e5 и тогда получим белый квадрат 5х5 с черным конем в центре (e5) и возможно в углу (зависит от расположения первого коня в жёлтом поле). В любом из этих случаев можно построить белый квадрат 5х5.
Т.о. если хотя бы один черный конь стоит в желтой области, то белый квадрат можно построить.
Если оба коня расположены в одной голубой области, то очевидно останется белый квадрат.
Пусть один чёрный конь расположен в одной голубой области, а второй конь - в другой голубой области. Не теряя общности, можно считать, что первый конь стоит в области B1. Если второй конь расположен в области B2 или B4, то на доске останется белый квадрат. Если же второй конь расположен в области B3, то первый конь может располагаться в клетках c4 или c5 и можно выделить белый квадрат 5х5 с чёрным центром в этой клетке, или первый конь стоит в других клетках области B1 и тогда можно построить белый квадрат с черными конями в угловых клетках.
Т.о. если оба коня стоят в голубой области, то белый квадрат также всегда можно построить.
Осталось рассмотреть 2 случая: оба чёрных коня находятся в квадрате С1; один конь голубой в области, а другой в C1.
Пусть оба коня находятся в области C1. Тогда с точностью до поворота возможно два варианта расположения коней.
Первый изображен на рисунке 3:
В этом случае очевидно можно построить белый квадрат.
Второй вариант расположения коней показан на рисунке 4:



Воспользовавшись идеей из обсуждения решения задачи 115, расположим на доске восьмиклеточные конфигурации так, чтобы в каждой конфигурации было ровно по одному чёрному коню. Любой квадрат 5х5 содержит как минимум одну конфигурацию (для проверки удобно передвигать по доске выделенный квадрат 5х5). Т.о. при таком расположении коней одноцветный квадрат получиться не может, и с учётом симметрии получим 4 варианта расположения коней, при которых построение одноцветного квадрата 5х5 невозможно.
Рассмотрим последний возможный вариант - один конь в голубой области, один конь в квадрате С1. В этом случае получаем с точностью до симметрии два варианта (рис.5 и рис. 6), когда построение одноцветного квадрата 5х5 невозможно:
Каждое расположение даст по 8 вариантов.
При других комбинациях получим либо квадрат с конем в угловой клетке, либо квадрат с конем в центральной клетке.

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

Обсуждение

Назовем две расстановки коней в каждом поле доски эквивалентными, если каждую из них можно получить из другой допустимыми преобразованиями.
Легко видеть, на доске 4х4 существует два класса эквивалентных между собой расстановок.
Эдвард Туркевич поставил вопрос о количестве классов для доски 8х8, Сергей Половинкин утверждает, что в этом случае классов не менее 64.

Награды

За составление задачи ММ117 Сергей Половинкин получает 7 призовых баллов. По столько же баллов за правильное решение задачи получают Алексей Волошин, Эдвард Туркевич, Анатолий Казмерчук и Дмитрий Пашуткин. Николай Дерюгин получает 4 призовых балла.

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

-- 01 дек 2009, 19:36 --

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

Текущее положение участников
в XII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|} \hline №& Участники& 111 & 112 & 113 & 114 & 115 & 116 & 117 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 12 & 9 & 7 & 55 \\ \hline 2.& Алексей Волошин & 2 & 6 & 11 & 7 & 11 & 6 & 7 & 50 \\ \hline 3.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 10 & 6 & 7 & 49 \\ \hline 4.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 10 & 6 & 7 & 43 \\ \hline 5.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 10 & 10 & 7 & 34 \\ \hline 6.& Николай Дерюгин & 3 & 4 & 9 & 7 & 4 & 0 & 4 & 31 \\ \hline 7.& Виктор Филимоненков & 2 & 6 & 10 & 7 & 0 & 0 & 0 & 25 \\ \hline 8.& Кирилл Веденский & 0 & 6 & 9 & 0 & 0 & 0 & 0 & 15 \\ \hline 9.& Юрий Вольвовский & 0 & 0 & 0 & 0 & 0 & 10 & 0 & 10 \\ \hline 10.& Илья Гермашев & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 7 \\ \hline 11.& Андрей Халявин & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 11.& Владислав Франк & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 13.& Александр Расстригин & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ \hline 14.& SiO2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline \end{tabular}$

[VAL]

Обратите внимание на немного изменившееся условие задачи ММ118.
В нем устранены погрешности, возникшие из-за невнимательности коллеги ведущего. Коллеге поставлено на вид!

[VAL]

Задача ММ118 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Задача о задаче (нестареющая классика на новый лад).

ММ118 (7 баллов)

Ведущий Математического марафона придумал задачу. Но, прежде чем помещать ее в Марафон, он решил протестировать задачу и рассказал ее своему коллеге:

- Бывшие одноклассники Петр и Николай встретились на мероприятии, посвященном 40-ю выпуска из школы, и разговорились.
П: Да-а... разбросала нас жизнь, 40 лет тебя не видел и ничего о тебе не слышал. А ведь раньше не разлей вода были, за одной партой сидели. Ну и как ты? Семьей обзавелся?
Н: А как же! У меня три красавца сына!
П: Ну ты даешь! И сколько же им лет?
Н: Надеюсь, ты по-прежнему любишь головоломки? Тогда догадайся сам. Сумма их возрастов равна номеру квартиры, в которой ты жил в школьные годы, а произведение возрастов равно...

... И ведущий Марафона для удобства коллеги написал нужное число на бумажке и продолжил:

- Петр достал ручку и на несколько минут погрузился в вычисления...
П: Ты знаешь, этих данных мне мало.
Н: Ах, да! Забыл добавить, что среднего я назвал в твою честь.
П: Спасибо! Теперь информации достаточно.
Сколько лет сыновьям Николая?

Коллега ведущего погрузился в вычисления (более продолжительные, чем Петр из задачи). Но его комментарий, не отличался от комментария Петра:
- Ты знаешь, этих данных мне мало - сказал он ведущему Марафона.
- Ах, да! - осознал ошибку ведущий - Тогда пусть Петром зовут не среднего, а старшего сына Николая.
- К сожалению, это не спасет задачу. А вот если Николай назовет Петром своего младшего сына, тогда задача будет иметь единственное решение!

Что за число написал ведущий?

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

Решение

Из реплики Петра следует, что искомое число (n) может быть представлено в виде произведения трех сомножителей, не превосходящих 40, с известной Петру, суммой.
Причем таких представлений более одного, но только в одном из них имеется среднее по величине число.
На основании комментария коллеги ведущего заключаем, что для искомого произведения таких сумм более одной.
Вот подходящие числа и соответствующие представления:
n = 720 (6 + 6 + 20 = 4 + 10 + 18 = 32, 6 + 8 + 15 = 5 + 12 + 12 = 29);
n = 1008 (6 + 6 + 28 = 3 + 16 + 21 = 40, 8 + 9 + 14 = 7 + 12 + 12 = 31);
n = 2800 (8 + 14 + 25 = 7 + 20 + 20 = 47, 10 + 10 + 28 = 7 + 16 + 25 = 48);
n = 2880 (6 + 15 + 32 = 5 + 24 + 24 = 53, 12 + 12 + 20 = 10 + 16 + 18 = 44);
n = 3600 (10 + 10 + 36 = 6 + 20 + 30 = 56, 10 + 15 + 24 = 9 + 20 + 20 = 12 + 12 + 25 = 49);
n = 5760 (12 + 12 + 40 = 8 + 20 + 36 = 64, 12 + 16 + 30 = 10 + 24 + 24 = 58);
n = 7200 (10 + 18 + 40 = 8 + 30 + 30 = 68, 15 + 15 + 32 = 12 + 20 + 30 = 62).
В шести из семи перечисленных случаев корректировка условия, предложенная ведущим, спасает задачу:
При n = 720 информация о наличии старшего позволяет Петру однозначно определить возрасты (6, 8, 15), только если номер квартиры был 29.
Аналогично при n = 1008 ответ - 8, 9, 14;
при n = 2800 - 8, 14, 25;
при n = 2880 - 6, 15, 32;
при n = 5760 - 12, 16, 30;
при n = 7200 - 10, 18, 40.
И лишь в случае, когда n = 3600, информация о наличии старшего не позволит Петру выбрать единственный вариант.
В то же время, если среди сыновей будет младший, то только при 56-м номере квартиры Петр (а вслед за ним и коллега ведущего) смогут однозначно определить возрасты - 6, 20 и 30.

Ответ: 3600

Обсуждение

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

Выбор числа 40 в качестве верхней границы возрастов сыновей Николая - довольно естественное (его выбрали практически все участники), но, все же, условное ограничение.
Увеличение этой границы до до сколько-нибудь разумных пределов (вдруг Николай по два года в одном классе сидел) добавляет еще один вариант (n = 6300 (10 + 15 + 42 = 7 = 30 + 30 = 67, 15 + 15 + 28 = 12 + 21 + 25 58)). но не нарушает однозначности решения.
И только допущение совсем уж фантастических возрастов сыновей (не менее 50 лет) приводит к дуалям.

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

И еще об одномм нюансе: Сергей Половинкин полагает, что, кроме приведенного, задачка имеет вырожденное, нулевое решение.
Аргументация Сергея: Допустим, что Петр знает произведение 0 и сумму 3 или 4. В каждом из этих случаев он сначала не может выбрать из вариантов ((0,1,2) и (0,0,3) для тройки) и ((0,1,3), (0,2,2) и (0,0,4) для четверки), а после получения информации о наличии среднего сына выбирает единственный подходящий вариант.
Соответственно, коллега ведущего не в состянии выбрать между вариантами (0,1,2) и (0,1,3). "Замена среднего сына старшим" не дает однозначности, а наличие младшего приводит к единственному варианту (0,1,2).
Я не рассматривал вариант с нулевым произведением, полагая, что достаточной защитой от этого побочного варианта являются следующие моменты в условии:
"ведущий Марафона для удобства коллеги написал нужное число на бумажке", "Петр достал ручку и на несколько минут погрузился в вычисления".
А Алексей Волошин рассмотрел. И забраковал на основании последней реплики коллеги ведущего. Действительно, если произведение возрастов сыновей Николая равно 0, то в случае, когда Петром зовут младшего сына, коллега ведущего получит два подходящих варианта: (0,1,1) и (0,1,2), т.е. решение будет не единственно.


Награды

За решение задачи ММ118 участникам начислены следующие призовые баллы:
Алексей Волошин - 8 призовых баллов;
Александр Ларин, Сергей Половинкин, Дмитрий Пашуткин, Эдвард Туркевич и Анатолий Казмерчук - по 7 баллов;
Николай Дерюгин - 6 баллов.
В этих оценкеах учтены, как поощрительные баллы за "своевременные сигналы", так и вычеты за некоторые шероховатости в решении.

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

[VAL]

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

Текущее положение участников
в XII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 12 & 9 & 7 & 7 & 62 \\ \hline 2.& Алексей Волошин & 2 & 6 & 11 & 7 & 11 & 6 & 7 & 8 & 58 \\ \hline 3.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 10 & 6 & 7 & 7 & 56 \\ \hline 4.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 10 & 6 & 7 & 7 & 50 \\ \hline 5.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 10 & 10 & 7 & 7 & 41 \\ \hline 6.& Николай Дерюгин & 3 & 4 & 9 & 7 & 4 & 0 & 4 & 6 & 37 \\ \hline 7.& Виктор Филимоненков & 2 & 6 & 10 & 7 & 0 & 0 & 0 & 0 & 25 \\ \hline 8.& Кирилл Веденский & 0 & 6 & 9 & 0 & 0 & 0 & 0 & 0 & 15 \\ \hline 9.& Юрий Вольвовский & 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 10 \\ \hline 10.& Илья Гермашев & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 0 & 7 \\ \hline 10.& Александр Ларин & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & 7 \\ \hline 12.& Андрей Халявин & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 12.& Владислав Франк & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 14.& Александр Расстригин & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ \hline 15.& SiO2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ \hline \end{tabular}$

[VAL]

===============
Задача ММ119 утратила статус конкурсной и может свободно обсуждаться.

ММ119 (Ш-5) (8 баллов)

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

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

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

Решение

Наилучшего результата добился Анатолий Казмерчук, предложивший позицию, в которой белые имеют 105 различных матующих ходов.



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

Обсуждение

В символический "клуб 100", вместе с Анатолием Казмерчуком, вошли Сергей Половинкин (101 мат) и Олег Деверенко, последовательно приславший три позиции, с которых мат ставился 98-ю, 99-ю и, наконец, ста способами.

Некоторые участники, по-видимому, неверно поняли условие, ограничившись рассмотрением позиций без превращенных фигур. Эдвард Туркевич указал, где можно найти такую позицию, в которой 47 матующих ходов: http://www.chess.hut.ru/children/007.html
Другое "самоограниечение" - помещение короля на край или даже в угол доски. Конкурсантов, пошедших таким путем, было немного.
Гораздо более растространенный ложный путь - ориентация позиции преимущественно на матующие ходы вскрытым шахом.
Признаюсь и я, предлагая задачу ММ119, пошел именно по такому пути. Логика ясна: при вскрытом шахе мат может даваться практически любым, а не специальным ходом фигуры, открывающей шах.
А если учесть, что ферзь, прячущийся за другой фигурой, способен матовать и собственными ходоми, становится понятным притягательность такого подхода. Победил в необъявленном подконкурсе "Вскрытый шах" Николай Дерюгин. 63 из 80-ти матующих ходов в предложенном им позиции - вскрытые шахи. Но этот привлекательный с виду путь оказался менее эффективным, чем опора на "бешеных" ферзей. Сергей Половинкин (в дополнение к оновному решению) указал позицию, в которой 9 ферзей без помощи других фигур дают 92 мата.
Ну а наилучший вариант примирил оба подхода. В нем нашлось место и вскрытым и "активным" шахам.

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



Итак один ферзь, удачно расположенный по отношению к королю, может дать 12 различных шахов. Это наглядно иллюстрирует мощь данной фигуры. Ведь ладья, слон и конь не могут дать более двух активных шахов. А король, естественно, и вовсе ни одного. Второе место в этом споре шахующих фигур уверенно занимает пешка. За счет взятий и превращений пешка может дать шах пятью различными способами.
Правда ферзь - единственная из фигур, не способная давать вскрытые шахи. По этому показателю лидирует ладья - 14 шахов. Совсем немного отстает слон - 13 шахов. 12-ю способами вскрытый шах может дать пешка (правда, матующими могут быть не более 8-ми вскрытых шахов, даваемых пешкой).
Конь может открыть шах 8-ю способами, а король - 6-ю.


Награды

При выставлении призовых баллов я, в первую очередь, исходил из достигнутого результата. Во вторую и третью очередь учитывались (но таки учитывались!) строгость обоснования корректности позиции и сопутствующие изыскания. В результате конкурсанты получили следующие призовые баллы:
Анатолий Казмерчук - 11 баллов;
Сергей Половинкин - 10 баллов;
Олег Деревенко - 9 баллов;
Николай Дерюгин - 8 баллов;
Алексей Волошин и Виктор Филимоненков - по 7 баллов;
Александр Расстригин - 6 баллов;
Эдвард Туркевич - 4 балла;
Кирилл Веденский - 3 балла.

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

[VAL]

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

Текущее положение участниковв XII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 12 & 9 & 7 & 7 & 10 & 72 \\ \hline 2.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 10 & 6 & 7 & 7 & 11 & 67 \\ \hline 3.& Алексей Волошин & 2 & 6 & 11 & 7 & 11 & 6 & 7 & 8 & 7 & 65 \\ \hline 4.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 10 & 6 & 7 & 7 & 4 & 54 \\ \hline 5.& Николай Дерюгин & 3 & 4 & 9 & 7 & 4 & 0 & 4 & 6 & 8 & 45 \\ \hline 6.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 10 & 10 & 7 & 7 & 0 & 41 \\ \hline 7.& Виктор Филимоненков & 2 & 6 & 10 & 7 & 0 & 0 & 0 & 0 & 7 & 32 \\ \hline 8.& Кирилл Веденский & 0 & 6 & 9 & 0 & 0 & 0 & 0 & 0 & 3 & 18 \\ \hline 9.& Юрий Вольвовский & 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 10 \\ \hline 10.& Олег Деревенко & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 & 9 \\ \hline 10.& Александр Расстригин & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 & 9 \\ \hline 12.& Илья Гермашев & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 0 & 0 & 7 \\ \hline 12.& Александр Ларин & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & 0 & 7 \\ \hline 14.& Андрей Халявин & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 14.& Владислав Франк & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 16.& SiO2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{tabular}$

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

Итоги тематического конкурса
$\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& Ш1 & Ш2 & Ш3 & Ш4 & Ш5 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 10 & 12 & 7 & 10 & 42 \\ \hline 2.& Анатолий Казмерчук & 3 & 10 & 10 & 7 & 11 & 41 \\ \hline 3.& Алексей Волошин & 2 & 11 & 11 & 7 & 7 & 38 \\ \hline 4.& Эдвард Туркевич & 2 & 8 & 10 & 7 & 4 & 31 \\ \hline 5.& Николай Дерюгин & 3 & 9 & 4 & 4 & 8 & 28 \\ \hline 6.& Виктор Филимоненков & 2 & 10 & 0 & 0 & 7 & 19 \\ \hline 7.& Дмитрий Пашуткин & 0 & 0 & 10 & 7 & 0 & 17 \\ \hline 8.& Кирилл Веденский & 0 & 9 & 0 & 0 & 3 & 12 \\ \hline 9.& Олег Деревенко & 0 & 0 & 0 & 0 & 9 & 9 \\ \hline 9.& Александр Расстригин & 3 & 0 & 0 & 0 & 6 & 9 \\ \hline 11.& SiO2 & 1 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{tabular}$

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

[VAL]

В связи с малым количеством (и не идеальным качеством) поступивших решений ММ120, срок приема решений продлевается до 2.02.10.

[kahey]

Где сама задача?

[VAL]

kahey в сообщении #284644 писал(а):

Где сама задача?

Тут.

[VAL]

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

В связи с малым количеством (и не идеальным качеством) поступивших решений ММ120, срок приема решений продлевается до 2.02.10.

А теперь до 5.02.10.
На это раз "по просьбам трудящихся"

[VAL]

Задача ММ120 утратила статус конкурсной и может свободно обсуждаться на форуме.

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

Задача ММ120 продолжает линию задачи ММ57 и тематического конкурса 11-го тура.

ММ120 (7 баллов)

В задаче ММ103 каждому выпуклому многоугольнику был поставлен в соответствие сопровождающий граф:
вершины графа - элементарные многоугольники, на которые разбивается исходный многоугольник своими диагоналями;
две вершины смежны, если соответствующие многоугольники имеют общую сторону.

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

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

Решение

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

С периферийными вершинами и диаметром дело обстоит достаточно просто. Легко понять, что периферийными вершинами сопровождающего графа будут элементарные треугольники, имеющие общую сторону с исходным многоугольником. При четном n наиболее удаленными друг от друга вершинами графа будут элементарные треугольники, примыкающие к противоположным сторонам исходного n-угольника (рис. 1), а при нечетном - к "наиболее противоположным".
Простой комбинаторный подсчет количества диагоналей, разделяющих такие элементарные треугольники, дает следующие значения диаметра:
$D=\frac{n^2-8}4$ для четных n и $D=\frac{n^2-9}4$ - для нечетных.


Итак, количество периферийных вершин и диаметр сопровождающего графа зависят только от числа сторон исходного многоугольника, а именно:
диаметр равен $\left[\frac{n^2-8}4\right]$, а число периферийных вершин сопровождающего графа равно n (при $n>3$).

Гораздо сложнее обстоит дело с радиусом и центральными вершинами сопровождающих графов.
Достаточно просто определить лишь наименьшее значение радиуса.
Сначала оратимся к исходным многоугольникам с нечетным числом сторон $(n=2k+1,\ k\in\mathbb{N})$. В этом случае для каждого k существует многоугольник, радиус которого равен $R=\frac{n^2-9}8$, т.е. половине диаметра. Это верно, например, для правильных многоугольников.
Диагонали многоугольника с нечетным числом сторон, соединяющие вершину с концами противолежащей стороны, будем называть "большими". Треугольники, высекаемые парами больших диагоналей, выходящих из одной вершины исходного многоугольника, будем называть "центральными секторами".
В общем случае радиус сопровождающего графа нечетноугольника будет равен половине диаметра тогда и только тогда, когда существует элементарный многоугольник, лежащий внутри всех центральных секторов.
На рисунке 2 такой элементарный многоугольник закрашен желтым цветом, а большие диагонали выделены красным.
Если такой элементарный многоугольник существует, то он является единственной центральной вершиной сопровождающего графа.


Заметим, что наши рассуждения будут верны и для $k = 1$. В этом случае "большими диагоналями" будут стороны треугольника, а сам треугольник будет центральным сектором для каждой своей вершины.
Однако, начиная с $k=4$, элементарный многоугольник, принадлежащий всем центральным секторам может и не существовать.
На рисунке 3 представлен такой девятиугольник. Элементарные многоугольники, являющиеся центральными вершинами сопровождающего графа, выделены желтым цветом.
Обратите внимание, что по пути из каждой центральной вершины в наиболее отдаленную от нее приходится преодолевать пять больших диагоналей (а для девятиугольника на рисунке 2 хватало четырех).


Используя тот же подход (назовем его "методом децентрации"), при подходящих k можно добиться сколь угодно большого превышения радиусом значения $\frac{D}2$.
Для этого подходят многоугольники, у которых не только большие диагонали, но и примыкающие к ним образуют секторы. имеющие пустое пересечение.
На рисунке 4 представлен 15-угольник, радиус сопровождающего графа которого равен 30, т.е. на 3 превосходит половину диаметра. 7 центральных вершин выделены желтым цветом.


Если же число сторон исходного многоугольника увеличить до 21, то можно построить многоугольник с радиусом графа равным 60, что на 6 больше половины диаметра.
На рисунке 5 представлен такой многоугольник (10 элементарных многоугольников, соответствующих центральным вершинам, цветом не выделены из-за малых размеров).


Обобщая случаи $n=9, \ n=15, \ n=21$, придем к выводу, что при $n=6k+3$ существует многоугольник, сопровождающий граф которого имеет радиус $5k(k+1)$ и $3k+1$ центральных вершин.
Я полагаю, что именно для многоугольников с числом сторон $6k+3$ имеет место наибыстрейший рост максимального радиуса, но точного доказательства этого факта у меня нет.
Если n не сравнимо с 3 по модулю 6, то радиус растет не так быстро, но сама идея децентрации, все равно, работает. Например, убрав пару вершин у 21-угольника с рисунка 5, можно получить 19-угольник, у которого радиус превышает половину диаметра на 3.

Перейдем к рассмотрению сопровождающих графов многоугольников с четным числом сторон.
Первым делом докажем, что в этом случае радиус не может равняться половине диаметра.
Для $n=4k+2$ это очевидно в силу нечетности диаметра. Но значение $R=\frac{n^2-4}8$ в этом случае достижимо.
Для получения подходящего многоугольника достаточно отрезать уголки у правильного многоугольника с нечетным числом сторон (рис.6).


Пусть теперь $n=4k$. Положим $r=\frac{D}2$.
Допустим, что у графа 4k-угольника есть вершина с эскцентриситетом r.
Тогда расстояние от этой вершины каждой периферийной вершины должно равняться r:
Оно не может быть больше r, поскольку r - это эксцентриситет, а если хотя бы одна периферийная вершина удалена меньше чем на r, то диаметр будет меньше 2r.
Но расстояния от любой вершины до периферийных вершин, примыкающих к соседним сторонам исходного многоугольника, имеют разную четность (в одном случае надо пересекать большую диагональ, выходящую из общей для данных сторон вершины многоугольника, а в другом - нет).
Полученное противоречие доказывает наше утверждение.
Наименьшим значением радиуса для $n=4k$ будет $R=\frac{D}2+1=\frac{n^2}8$. Подходящий 4k-угольник можно получить из правильного 2k-угольника, отрезав от него маленькие уголки: k совсем малюсенькиx, а k других чуть побольше (см. рис.7)


Большие диагонали многоугольника с четным числом сторон ($n=2k$) могут пересекаться в одной точке (например, в правильном многоугольнике). Это приводит к образованию в сопровождающем графе цикла длины n. Необходимость "обходить эту дыру" (см. рис. 8) приводит к увеличению радиуса на $\left[\frac{n}4\right]$.


Гипотеза, высказанная несколькими конкурсантами (к ней склонялся и я на ранней стадии составления задачи), "наибольшее значение радиуса сопровождающего графа 2k-угольника достигается для правильных многоугольников и равно $\frac{n^8+2n-8}8$" не верна для почти всех k.
Ведь превышение радиуса над половиной диаметра растет для графов правильных 2k-угольников линейно относительно числа сторон, в то время как метод децентрации (а он применим и для разбираемого случая), дает рост по квадратичному закону.
Впервые четноугольник, построенный по методу децентрации, приводит к графу, радиус которого превышает радиус графа правильнгого многоугольника с тем же числом сторон при $n = 24$
Посмотреть (но не рассмотреть :)) его можно на рисунке 9. Его радиус (равный, например, расстоянию от желтого элементарного треугольника в центре, до элементарного треугольника, примыкающего к стороне 5-6) равен 79, в то время как радиус графа правильного 24-угольника равен 77.


Ситуация с центральными вершинами достаточно сложна. Единственную центральную вершину имеют графы треугольников, пятиугольников и семиугольников.
У графа четырехугольника все 4 вершины центральные. Для остальных n количество центральных вершин может быть различным.
Например, у графа шестиугольника одна либо шесть центральных вершин. А у графа восьми угольника может быть две, три или восемь центральных вершин (см. рис. 10-12).
Для общего случая справедливы такие утверждения:
При n, не кратном 4, существуют многоугольник, граф которого имеет единственную центральную вершину;
При четном n существует многоугольник, граф которого имеет n центральных вершин.
Больше чем n центральных вершин граф n-угольника иметь, по-видимому, не может.







Обсуждение

Единственную центральную вершину может иметь и граф 12-угольника. 16-угольников с таким свойством я не нашел. Не исключено, что графа с единственной центральной вершиной не существует тогда и только тогда, когда число сторон соответствующего многоугольника - степень двойки.

Анонсируя задачу, я заявил, что она имеет прямое отношение не только к ММ57 и к тематическим задачам 11-го тура, но и еще к одной марафонской задаче. Чтобы убедиться в справедливости этого утверждения достаточно сравнить выражение для диаметра сопровождающего графа с верхней гранью диапазона отношения суммы длин диагоналей к периметру выпуклого многоугольника, вычисленной в задаче ММ2.

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

Номинал в 7 баллов был назначен для ММ120 дабы не спугнуть участников :)
На самом деле 7 баллов планировалось ставить тем участникам, которые разберутся с диаметром и заметят непостоянство радиуса для многоугольников с нечетным числом сторон. В итоге я почти угадал :)

При подведении итогов я столкнулся дилеммой.
Чье решение лучше:
того участника, который больше нашел больше других, но при этом кое-в чем ошибся;
того, который не ошибался (реже ошибался), но при этом и обнаружил меньше локальных закономерностей?
Если добавить сюда, что строгость обоснований тоже разнится, станет понятно, с какими трудностями я столкнулся. Так что, не обессудьте!

Ясно, что точку ставить рано. Получены (а тем более обоснованы) ответы не на все вопросы задачи. Кроме того, возникает целый ряд новых вопросов. В общем, есть что пообсуждать.
Если же обсуждение (по не самой лучшей марафонской традиции) не завяжется, пеняйте на себя. Новые встречи с выпуклыми многоугольниками и их графами вам гарантированы! :)

Награды

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

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

[VAL]

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

Итоговое положение участников в XII туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 10 & 8 & 12 & 9 & 7 & 7 & 10 & 8 & 80 \\ \hline 2.& Анатолий Казмерчук & 3 & 6 & 10 & 7 & 10 & 6 & 7 & 7 & 11 & 7 & 74 \\ \hline 3.& Алексей Волошин & 2 & 6 & 11 & 7 & 11 & 6 & 7 & 8 & 7 & 7 & 72 \\ \hline 4.& Эдвард Туркевич & 2 & 3 & 8 & 7 & 10 & 6 & 7 & 7 & 4 & 0 & 54 \\ \hline 5.& Николай Дерюгин & 3 & 4 & 9 & 7 & 4 & 0 & 4 & 6 & 8 & 4 & 49 \\ \hline 6.& Дмитрий Пашуткин & 0 & 0 & 0 & 7 & 10 & 10 & 7 & 7 & 0 & 0 & 41 \\ \hline 7.& Виктор Филимоненков & 2 & 6 & 10 & 7 & 0 & 0 & 0 & 0 & 7 & 0 & 32 \\ \hline 8.& Кирилл Веденский & 0 & 6 & 9 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 18 \\ \hline 9.& Юрий Вольвовский & 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 10 \\ \hline 10.& Олег Деревенко & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 & 0 & 9 \\ \hline 10.& Александр Расстригин & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 & 0 & 9 \\ \hline 12.& Илья Гермашев & 0 & 0 & 0 & 7 & 0 & 0 & 0 & 0 & 0 & 0 & 7 \\ \hline 12.& Александр Ларин & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & 0 & 0 & 7 \\ \hline 14.& Андрей Халявин & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 14.& Владислав Франк & 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 6 \\ \hline 16.& SiO2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline \end{tabular}$

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