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

[VAL]

Завершен XXIII конкурс в рамках Математического марафона.
По ходу конкурса участники разбились на микрогруппы (преимущественно пары), в рамках которых и протекала борьба.
Единственное место, за которое особой борьбы не было... Впрочем, все видно из таблицы.

Итоговое положение участников в XXIII конкурса в рамках Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 221 & 222 & 223 & 224 & 225 & 226 & 227 & 228 & 229 & 230 & \Sigma \\ \hline & \textit{Номинал задачи} & \textit{4} & \textit{6} & \textit{6} & \textit{6} & \textit{6} & \textit{5} & \textit{7} & \textit{4} & \textit{7} & \textit{15} & \textit{66} \\ \hline 1.& Олег Полубасов & 4 & 3 & 7 & 8 & 6 & 9 & 9 & 6 & 8 & 20 & 80 \\ \hline 2.& Анатолий Казмерчук & 5 & 6 & 6 & 7 & 7 & 8 & 8 & 6 & 9 & 17 & 79 \\ \hline 3.& Валентина Колыбасова & 4 & 6 & 6 & 6 & 6 & 5 & 7 & 4 & 6 & 4 & 54 \\ \hline 4.& Виктор Филимоненков & 4 & 3 & 6 & 6 & 6 & 5 & 7 & 4 & 7 & 5 & 53 \\ \hline 5.& Евгений Гужавин & 4 & 3 & 7 & 6 & 6 & 7 & 6 & - & - & - & 39 \\ \hline 6.& Владислав Франк & 4 & 4 & 3 & 7 & 6 & 6 & 7 & - & - & - & 37 \\ \hline 7.& Владимир Дорофеев & 4 & 5 & 2 & 6 & 6 & 6 & 7 & - & - & - & 36 \\ \hline 8.& Дмитрий Курашкин & 2 & - & - & - & 6 & 5 & - & - & - & - & 13 \\ \hline 9.& Тимофей Игнатьев & - & - & - & - & - & 5 & 7 & - & - & - & 12 \\ \hline 10.& Василий Дзюбенко & - & 2 & - & - & - & - & - & - & - & - & 2 \\ \hline \end{tabular}

Мои поздравления победителям!
Спасибо, всем участникам!

-- 10 дек 2017, 11:27 --

А вот как выглядят суммарные успехи конкурсантов по итогам всех прошедших конкурсов.

Положение лидирующей группы после 23-го конкурса Марафона
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|r|r|c|} \hline Участники \ \ Туры$\to$ &1-11&12&13&14&15&16&17&18&19&20&21&22&23&\Sigma\\ \hline 1. А.Казмерчук &183&74&61&45&54&53&51&73&79&69&82&85&79&988\\ \hline 2. О.Полубасов &268&-&-&-&-&64&56&83&97&73&79&87&80&887\\ \hline 3. В.Филимоненков &262&32&22&-&48&55&46&71&53&62&23&36&53&762\\ \hline 4. С.Половинкин &-&80&57&64&56&58&41&74&60&63&36&2&-&591\\ \hline 5. В.Франк &379&6&-&26&-&-&-&-&-&-&-&69&37&517\\ \hline 6. А.Волошин &65&72&61&47&52&54&50&76&3&-&-&-&-&480\\ \hline 7. Н.Дерюгин &51&49&21&20&19&43&18&54&21&4&-&-&-&300\\ \hline 8. Д.Пашуткин &-&41&16&48&43&24&3&-&45&54&-&25&-&293\\ \hline 9. E.Гужавин &-&-&4&34&9&9&21&34&17&-&18&-&39&165\\ \hline 10. В. Колыбасова &-&-&-&-&-&-&-&-&10&57&17&-&54&138\\ \hline 11. А.Халявин &66&6&-&-&43&-&-&-&14&-&-&-&-&129\\ \hline 12. А.Богданов &112&-&-&-&-&-&-&-&-&-&-&-&-&112\\ \hline 13. К.Веденский &30&18&-&17&20&-&-&23&-&-&-&-&-&108\\ \hline 14. А.Извалов &46&-&-&-&-&-&-&34&-&-&15&-&-&95\\ \hline 15. В.Дорофеев &-&-&-&-&-&-&-&-&9&21&10&18&36&94\\ \hline 16. А.Никонов &80&-&-&-&-&-&-&-&38&40&2&9&-&89\\ \hline 17. И.Козначеев &88&-&-&-&-&-&-&-&-&-&-&-&-&88\\ \hline 18. К.Кноп &75&-&-&-&-&-&-&-&-&10&-&-&-&85\\ \hline 19. Б.Бух &81&-&-&-&-&-&-&-&-&-&-&-&-&81\\ \hline 20. М.Алексеев &80&-&-&-&-&-&-&-&-&-&-&-&-&80\\ \hline 21. Э.Туркевич &9&54&11&-&-&-&-&-&-&-&-&-&-&74\\ \hline 22. А.Винокуров &73&-&-&-&-&-&-&-&-&-&-&-&-&73\\ \hline 22. Д.Милосердов &73&-&-&-&-&-&-&-&-&-&-&-&-&73\\ \hline 24. А.Ларин &-&-&7&-&31&29&-&-&-&-&-&-&-&67\\ \hline 25. Е.Машеров &45&-&5&-&4&10&-&-&10&-&-&-&-&64\\ \hline \end{tabular}

Валентина Колыбасова ворвалась в топ-10, украсив сугубо мужскую (до того) компанию.

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

[Ariadna H]

Ура-ура!

[Masik]

Спасибо ведущему за очередной тур Марафона! В первой задаче изюминки я не обнаружил, а остальные задачи наскоком не решались, а требовали анализа и исследования подходов с разных сторон, за что я и люблю этот конкурс. Как всегда, задачи были разнообразными. Задачи на условную вероятность – не частые гости в Марафоне. Наверное, надо их приглашать почаще, тем более что многие из них имеют интуитивно неожиданные ответы. Геометрическая задача, как обычно, вызвала некоторые затруднения. Но гвоздём программы, конечно, выступает цуг комбинаторных задач. На удивление, в Сети мне удалось найти очень мало материалов, связанных с исследованиями конфигураций прямых общего положения. В частности, вот я доказал, что внешний контур любой конфигурации n > 3 прямых содержит не менее 2n-2 элементарных отрезка. А насколько ценен этот результат – не понятно. Может, он тривиален, а может, заслуживает публикации в виде статьи.
Не согласен, что «после решения ММ228-230 круг нерешенных задач, связанных с конфигурациями прямых общего положения, скорее расширился, чем наоборот». Когда я приступил к решению ММ228, эта область была для меня тёмным лесом, а сейчас я в ней уже уверенно ориентируюсь (это стандартная фраза дилетанта ). Например, мне очевидно, что любую конфигурацию n прямых можно перевести в любую другую, пользуясь только одной операцией – «флипом треугольников». Если потребуется найти какую-нибудь конфигурацию с заданным свойством или перебрать все такие конфигурации машинным способом, то я уже представляю, как это смоделировать. Кстати, никакого программирования в этом туре не потребовалось, что считаю хорошей тенденцией. Трёх комбинаторных задач маловато, только-только разбежался – и уже финиш. Может быть, стоило пожертвовать ММ221.
В целом, ведущему чмоки-чмоки, всем участникам счастливого Нового Года и успехов в следующих турах Марафона! Будьте здоровыми и умненькими!

[VAL]

Masik в сообщении #1274730 писал(а):

Спасибо ведущему за очередной тур Марафона!

Спасибо участникам! Без них (вас) было бы скучновато.

Цитата:

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

Но кое-что, все же, есть.
А вот на задачу ММ200 (триангуляция треугольника прямыми) я с удивлением не обнаружил ничего!

Цитата:

В частности, вот я доказал, что внешний контур любой конфигурации n > 3 прямых содержит не менее 2n-2 элементарных отрезка. А насколько ценен этот результат – не понятно. Может, он тривиален, а может, заслуживает публикации в виде статьи.

Есть мнение (классическая формулировка ), что этот результат тривиален.

Цитата:

Не согласен, что «после решения ММ228-230 круг нерешенных задач, связанных с конфигурациями прямых общего положения, скорее расширился, чем наоборот».

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

Цитата:

Когда я приступил к решению ММ228, эта область была для меня тёмным лесом, а сейчас я в ней уже уверенно ориентируюсь (это стандартная фраза дилетанта ). Например, мне очевидно, что любую конфигурацию n прямых можно перевести в любую другую, пользуясь только одной операцией – «флипом треугольников».

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

Цитата:

Трёх комбинаторных задач маловато, только-только разбежался – и уже финиш.

У меня еще есть немного в загашнике. Но тут важно не переборщить.

Цитата:

Может быть, стоило пожертвовать ММ221.

Не думаю, что это верно.
Достаточно посмотреть количество решений, присланных на ММ221 и ММ230.
Понимаю, что для "зубров" ММ221 вполне рутинна. Но хотелось бы, чтобы круг конкурсантов не ограничивался одними "зубрами". Тем более, что зубры не даром занесены в Красную книгу.
Так что, как и обещал, буду стараться выдерживать баланс, чтобы и сторонникам ММ230 было чем заняться, и других конкурсантов не распугать.

Цитата:

В целом, ведущему чмоки-чмоки, всем участникам счастливого Нового Года и успехов в следующих турах Марафона! Будьте здоровыми и умненькими!

Присоединяюсь к этим пожеланиям!

[Masik]

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

Цитата:

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

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

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

[VAL]

Почитал про эту самую имитацию отжига.
Сильно продвинулся в химии и кристаллографии.
С алгоритмом пока не разобрался.

[Masik]

«Допустим, что вы решили начать своё восхождение на гору, проснувшись утром в отеле на горнолыжном курорте. Ближайшей высшей точкой будет верхний этаж отеля, а потом его крыша. А дальше вам идти некуда. Чтобы взобраться на вершину горы, вам нужно сначала выйти на улицу, для чего придётся спуститься на первый этаж отеля. Но это нарушает требование, чтобы каждый шаг по-вышал ваше местонахождение.»
Стивен Скиена
Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: Пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с.: ил.

Физические аналогии только затуманивают суть метода имитации отжига. А суть такова: начав с какой-то точки, путник делает случайный шаг в локальную окрестность. Если новая точка не хуже (в рассматриваемом примере - не ниже) прежней, шаг принимается. Иначе путник обращается к датчику случайных чисел. В начале пути ДСЧ добрый и разрешает шаги с большой вероятностью, но постепенно ДСЧ становится менее добрым (температура понижается). В конце пути разрешаются только улучшающие шаги.
Чтобы такой случайный поиск сработал, путник должен совершить своё путешествие очень много раз. Поэтому требуются два условия: 1. шаг нужно уметь делать быстро. 2. Оценку новой точки нужно получать очень быстро. И всё! Другие эвристические методы обычно требуют куда большего числа условий.
Например, пусть мы хотим найти конфигурацию с минимумом четырёхугольников. Начав с произвольной конфигурации будем делать случайные разрешённые флипы треугольников (как отличить разрешённые флипы от запрещённых, я пока не знаю, но это дело наживное). Флип треугольника затрагивает не более 6 соседних граней, то есть, операция константная. Значит, метод имитации отжига здесь очень перспективен.
Теоретики доказали, что при очень медленном понижении температуры метод даже гарантирует достоверное достижение глобального оптимума. К сожалению, число путешествий в этом случае будет экспоненциальным, поэтому на практике применяется быстрое понижение температуры, которое получило название "тушение". Метод очень простой и очень эффективный. Так, в заочном чемпионате России по решению головоломок 2016 г. была задача 4, для решения которой перебор был совершенно необъятен. Я победил только благодаря методу имитации отжига. Он дал прекрасное решение, несмотря на то что целевая функция изобиловала локальными экстремумами.

[VAL]

Спасибо!
Без лишней химии действительно понятнее.

[VAL]

Всех марафонцев и сочувствующих с наступающим!

Пусть новый год принесет вам поменьше огорчений и побольше радости! (Над последним я работаю.)

[rockclimber]

Извините, стоило написать эту просьбу еще пару месяцев назад, но вот не догадался... А можно в этом году стартануть марафон числа так с первого апреля? В кои-то веки уезжаю в отпуск без детей на целую неделю. В прошлый раз такое удовольствие у меня было аж 8 лет назад (написал и сам ужаснулся).

-- 29.03.2018, 01:43 --

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

[VAL]

rockclimber в сообщении #1300266 писал(а):

А можно в этом году стартануть марафон числа так с первого апреля?

Сложновато будет...
Части задач у меня еще и нулевом приближении нет.
А те, что есть, пока сырые.

[rockclimber]

Ну не страшно. Всего-то 10 лет осталось подождать, когда младший ребенок самостоятельным станет :)

[Masik]

rockclimber в сообщении #1300372 писал(а):

Ну не страшно. Всего-то 10 лет осталось подождать, когда младший ребенок самостоятельным станет :)

Если будете решать марафонские задачи вместе с детьми, то через 10 лет они станут заядлыми марафонщиками.

[VAL]

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

rockclimber в сообщении #1300266 писал(а):

А можно в этом году стартануть марафон числа так с первого апреля?

Сложновато будет...
Части задач у меня еще и нулевом приближении нет.
А те, что есть, пока сырые.

А с другой стороны, почему бы и нет?
Для этого даже правила менять не придется. Вот выдержка:

Цитата:

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

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

Итак, поехали!

===========ММ236===============

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

Решения принимаются до 20.10.2018

Найти наименьшее натуральное $k$ такое, число $k\cdot2^n+1$ является составным при любом натуральном $n$.

===========ММ237===============

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

Решения принимаются до 27.10.2018

У Васи есть плоская квадратная коробка со стороной 40 см. Он хочет упаковать в нее две круглые плоские пиццы одинакового диаметра. Пиццы нельзя деформировать и накладывать друг на друга. Но одну из них можно разрезать одним прямолинейным разрезом. При таком наибольшем диаметре пицц это возможно?

===========ММ238===============

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

Решения принимаются до 3.11.2018

Доказать, что $\sum_{n=1}^\infty \frac{1}{n^3(\sin n)^2} < 10\pi$.

===========ММ239===============

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

Решения принимаются до 17.11.2018

Привести пример треугольника с целочисленными сторонами, медианами и площадью.

===========ММ240===============

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

Решения принимаются до 31.11.2018

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

[grizzly]

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

Доказать, что $\sum_{n=1}^\infty \frac{1}{n^3(\sin n)^2} < 10\pi$

Просьба проверить условие, поскольку эта задача является известной открытой проблемой (см., например, эту работу maxal).