Математический Марафон

[VAL]

===========ММ194===============
 
ММ194 (6 баллов)
Из n натуральных чисел, идущих подряд, выбрали 6 и разбили их на две тройки. При этом оказалось, что площади треугольников, стороны которых равны числам из этих троек, равны. При каком наименьшем n возможна такая ситуация?
Решение
Приведу решения Сергея Половинкина, а также (куда же без них?) Ариадны и Олега Полубасова.
Обсуждение
В идейном плане все присланные  решения близки: формула Герона и дале конечный перебор до нахождения подходящего n.
Однако оптимизация этого перебора в разных решениях существенно различна.
Покажу, maple-код перебора (для n=8), который осуществлял я:

Код: Выбрать все

[code]with(combinat):s:=(a,b,c)->expand((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)):
 C:=choose(6,2):  for c in C do S:=[n]:for i to 6 do if not member(i,c) then S:=[op(S),n+i] fi od:
 S:=[op(S),n+7]:Sp:=setpartition(S,3):
 for p in Sp do
 ss:=[solve(s(op(p[1]))-s(op(p[2])))]:
 for q in ss do r:=subs(n=q,s(op(p[1]))):
 if type(q,posint) and r>0 then print(subs(n=q,p),sqrt(r)/4) fi od od od:
                                                     1/2
                [[31, 36, 37], [32, 34, 38]], 24 455
  
                                                 1/2
                                             15 7
                    [[3, 8, 10], [4, 5, 6]], -------
                                                4  
[/code]

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

Награды
После некоторых размышлений решил никого не выделять. Константин Хадаев, Виктор Филимоненков, Ариадна, Олег Полубасов, Дмитрий Пашуткин, Анатолий Казмерчук, Антон Никонов и Сергей Половинкин - получают по 6 призовых баллов.
Эстетическая оценка задачи - 4.8 балла
 



[img]/modules/file/icons/application-octet-stream.png[/img] mm194.rar

[VAL]

===========ММ195===============
 
ММ195 (7 баллов)
Доказать, что для любого натурального числа n, найдется натуральное m, такое что существует не менее n треугольников с целочисленными сторонами и медианой m.
Решение
Приведу решения Дмитрия Пашуткина (наиболее типичное), Константина Хадаева (тоже очень короткое) и Олега Полубасова (с оценками зависимости между n и m).
Решение Константина Хадаева:

MM195
Рассмотрим прямоугольный пифагоров треугольник со сторонами , медиана равна . Поэтому достаточно, чтобы  представлялось в виде суммы квадратов достаточно большим числом способов. Известно, что если , где , то количество представлений равно , что можно сделать сколь угодно большим, поскольку простых вида  бесконечно много.

Обсуждение
Почему эта достаточно простая задача оценена в 7 баллов?
Дело в том, что изначально я планировал указать в формулировке, что треугольники должны быть разносторонними. Но (как со мной это нередко бывает) забыл. Я хотел было уточнить условие, но тут поступило решение Константина Хадаева, которое, с было весьма простым, но не опиралось на равнобедренные треугольники (хотя, по сути, решение Константина, как большинство присланных решений опирается на рассмотрение пифагоровых троек). После этого менять условие не имело смысла.
Любопытно, что большинство участников для получения требуемого результата обошлись не просто пифагоровыми тройками, а тройками, в которых один из катетов - степень двойки.
В решении Антона Никонова по сути рассмотрены случаи d = 2 и d = 4 из решения Олега Полубасова.
Последовательность из решения Олега Полубасова безусловно должна попасть в OEIS. Предлагаю Олегу добавить ее туда. В противном случае сделаю это сам.
Награды
За углубленное решение задачи ММ195 Олег Полубасов получает 10 призовых баллов, Антон Никонов - 9 призовых баллов. За правильное решение задачи Константин Хадаев, Виктор Филимоненков, Ариадна, Дмитрий Пашуткин, Анатолий Казмерчук и Сергей Половинкин - получают по 7 призовых баллов.
Эстетическая оценка задачи - 4.5 балла
 



[img]/modules/file/icons/application-octet-stream.png[/img] mm195.rar

[VAL]

===========ММ196==============
Задача ММ 196 составлена Олегом Полубасовым по мотивам ММ186
ММ196 (9 баллов)
1.   Три корабля A, B, и C движутся равномерно и прямолинейно.
2.   Когда корабль A находился ближе всего к маяку, расстояние между B и C было 30 миль.
3.   Когда корабль B находился ближе всего к маяку, расстояние между A и C было 40 миль.
4.   Когда корабль C находился ближе всего к маяку, расстояние между A и B было 14 миль.
5.   В 12:00 расстояния от маяка до всех кораблей были одинаковыми.
6.   В 13:00 расстояния от маяка до всех кораблей были одинаковыми.
7.   В 14:00 расстояния от маяка до всех кораблей были одинаковыми.
8.   В 15:00 корабль B пересек маршрут корабля A.
9.   В 16:00 корабль A пересек маршрут корабля B.
Найти скорость каждого корабля.
Примечание: Все корабли и маяк - материальные точки.
Решение
Приведу решения Сергея Половинкина, Константина Кнопа и Ариадны и авторское решение Олега Полубасова.
[b]Обсуждение
Наконец-то, Марафон внес свой вклад в решение задачи трех тел. Осталось всего ничего: изменить размерность, учесть гравитацию...

Я испытывал некоторые затруднения при "раздаче слонов".
Правильно ли давать автору задачи столько же  баллов, чем тому, кто ее всего лишь решил?
Заглянул в архивы. И нашел как подтверждение (ММ72), так и опровержение этого тезиса (ММ43). Однако во втором случае в авторском решении нашлось некое углубление задачи.
Еще сложнее, было оценить решение Антона Никонова.
С одной стороны, он существенно обобщил задачу.
С другой стороны, его решение нерационально.
С третьей (или снова с первой?) стороны, героический труд должен быть как-то оценен.
С четвертой (или снова со второй?) стороны, этот героический труд во многом был проделан еще при обобщении ММ186...
Итог моих сомнений отражен в следующем разделе.
Награды
За составление задачи ММ196 Олег Полубасов получает 9 призовых баллов. За решение и обобщение задачи Антон Никонов и Константин Кноп получают по 10 призовых баллов, а Виктор Филимоненков, Сергей Половинкин, Ариадна, Анатолий Казмерчук и Дмитрий Пашуткин - по 9 призовых баллов.
Эстетическая оценка задачи - 4.8 балла
 



[img]/modules/file/icons/application-octet-stream.png[/img] mm196.rar

[VAL]

===========ММ197===============
ММ197 (5 баллов)
Будем говорить, что n-угольник относится к классу k, если его можно разрезать на k треугольников одной прямой и нельзя разрезать одной прямой на большее число треугольников. Найти все возможные значения k для .
Примечания:
1. Никаких других фигур при разрезании возникать не должно.
2. Если вышеописанный разрез осуществить нельзя, многоугольник относится к классу 0.

Решение
Привожу только одно решение ММ197, поскольку остальные правильные решения идентичны приведенному.
Обсуждение
К моему удивлению, эта задача, представлявшаяся мне достаточно простой, вызвала затруднения даже у некоторых "зубров" Марафона.
Не все участники догадались, что линия разреза может целиком содержать некоторые стороны многоугольника.
Другие не заметили, что крайние точки разреза могут быть как вершинами, как и внутренними точками сторон.
За еще одну потерю (случай k=0) я оценку не снижал, поскольку в первоначальном варианте условия (не приводившем к классификации n-угольников) этот случай не возникал, а часть решений поступила еще до уточнения условия.
Дополнительный балл начислен Олегу Полубасову за некое обобщение задачи. Аналогичное обобщение есть в решении Владимира Дорофеева, но его дополнительный балл "сократился" с баллом изъятым за погрешности в изложении решения.
Награды
За решение задачи ММ197 участникам начислены следующие призовые баллы:
Олег Полубасов получает - 6;
Константин Хадаев, Виктор Филимоненков, Владимир Дорофеев, Сергей Половинкин и Дмитрий Пашуткин - по 5;  
Ариадна - 4;
Анатолий Казмерчук - 2;
Антон Никонов - 1;,
Эстетическая оценка задачи - 4.9 балла
 




[img]/modules/file/icons/application-octet-stream.png[/img] MM197_Полубасов.rar

[VAL]

===========ММ198===============
 
ММ198 (8 баллов)
Будем говорить, что n-угольник относится к классу s, если его можно триангулировать на n-2 треугольника внутренними диагоналями в точности s различными способами. Найти три наименьших и три наибольших значения s для n = 20.
Решение
Привожу решения Виктора Филимоненкова, Олега Полубасова и Анатолия Казмерчука.
Обсуждение
На ММ198 получено наименьшее в 20-м туре количество решений. По-видимому, это свидетельствует о трудности задачи (первоначальная цена задачи - показатель весьма субъективный). Альтернативное объяснение - задача не вызвала интереса участников - не проходит, ввиду максимально возможной эстетической оценки задачи.  Хотя... процитирую комментарий Дмитрия Пашуткина "Мне показалось, что  эта задача из тех, интерес к которым растет прямо пропорционально времени, затраченному на их решение, из разряда "аппетит приходит во время еды" Условие на первый взгляд создает впечатление громоздкости требуемых для решения построений, но стоит только взяться и дальше уже оторваться невозможно."
Отмечу два разных подхода, примененных участниками к конструированию нужных многоугольников: "склеивание" многоугольников с меньшим числом сторон по общей стороне; "вдавливание" некоторых вершин выпуклого многоугольника.
Для получения максимальных значений s конкурсанты естественно использовали второй подход. Для малых значений s большинство конкурсантов использовали первый подход и "уперлись" в случай s=11. В то время как "вдавливание" (см. решение Олега Полубасова) позволяет легко преодолеть этот барьер.
В некоторых решениях (например, у Анатолия Казмерчука) приведены (достаточно легко находимые) полные списки возможных значений s для n\le 6. Усилю этот результат, списком для n=7:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 23, 28, 42}.
Разумеется, можно продвинуться и дальше. Но задача описания всех возможных значений s (или хотя бы их количества) для произвольного "n", мягко говоря, очень трудна.
Рост n приводит некому "фрактально-комбинаторному взрыву". "Фрактально" - потому что в формулах для подсчета плодятся самоподобные подформулы. А "взрыву" - потому что плодятся они весьма активно.
Затруднено даже продвижение в изучении максимально возможных значений s. Это затруднение вызвано тем, что с ростом n, значения s, полученные однотипным формулам могут меняться местами (иногда совпадая).
Этот момент описан в решении Анатолия Казмерчука: Действительно, подставляя разные n в формулы  и  (соответствующие возможным классам n-угольников) получим:
для n=7 18 и 19 соответственно;
для n=8 оба раза по 62;
для n=9 213 и 207.  
Очередной раз я испытывал определенные затруднения при распределении призовых баллов. Предвосхищая чаяния ведущего, многие участники не ограничились шестью требуемыми значениями s. Понятно, что их усилия должны быть поощрены дополнительными баллами. В значительно меньшей степени понятно что лучше: продвинуться в нахождении больших значений дальше конкурентов, но при этом пропустить некоторые значения в "гарантированном" списке, или ограничиться меньшим количеством значений s, не доходя до пропущенного значения. Итоги моих сомнений см. в разделе "Награды".
А здесь приведу первый (если я тоже чего-то не пропустил) пропущенный случай в "гарантированном" списке Олега.
У 20-угольника на рисунке 1 отсутствуют внешние диагонали $$ %u0438 $$. Поэтому он относится к классу

Если же немного сместить вправо вершину  (рис. 2), то исчезнут триангуляции, содержащие диагональ . Это в точности триангуляции выпуклого 18-угольника . Поэтому у 20-угольника на рисунке 2 в точности триангуляций.
Награды
За решение задачи ММ198 участникам начислены следующие призовые баллы:
Олег Полубасов и Анатолий Казмерчук - по 11;
Сергей Половинкин - 10;
Виктор Филимоненков и Дмитрий Пашуткин - по 8;  
Ариадна - 6.
Эстетическая оценка задачи - 5 баллов
 




[img]/modules/file/icons/application-octet-stream.png[/img] mm198.rar

[VAL]

===========ММ199===============
В задаче ММ199 рассматриваются многоугольники, которые могут иметь многоугольные "дыры". Будем говорить, что данный многоугольник имеет род m, если у него m многоугольных дыр. (В частности, в ММ197 и ММ198 рассматриваются многоугольники рода 0.)
 
ММ199 (5 баллов)
Сколькими внутренними диагоналями и на сколько треугольников триангулируется n-угольник рода m?
Решение
Привожу решения Сергея Половинкина, Ариадны и Анатолия Казмерчука.
Обсуждение
Задача ММ199 не вызвала затруднений у конкурсантов. При этом методы решения были довольно разнообразны (см. приведенные решения).
Владимир Дорофеев указал, как считать стороны и вершины, в случае "двуугольных" и "одноугольных" дыр, чтобы ответы n+3m-3 и n+2m-2 оставались верными.
В то же время, Сергей Половинкин указал частные случаи многоугольников с "нормальными" дырами, в которых ответы n+3m-3 и n+2m-2 перестают быть верными (точнее, единственно верными). Хотя, разумеется, они останутся незыблемы и в этих случаях, если аккуратнее определить триангуляцию многоугольника диагоналями.

Награды
За решение задачи ММ199 Сергей Половинкин и Владимир Дорофеев получают по 6 призовых баллов, а Константин Хадаев, Виктор Филимоненков, Олег Полубасов, Дмитрий Пашуткин, Ариадна и Анатолий Казмерчук - по 5 призовых баллов.
Эстетическая оценка задачи - 4.6 балла
 



[img]/modules/file/icons/application-octet-stream.png[/img] 199.rar

[VAL]

===========ММ200===============
 
ММ200 (8 баллов)
Обозначим через T(m) максимально возможное количество треугольников, на которые можно разрезать треугольник m прямыми. (Никаких других фигур, при разрезании возникать не должно.)
При каком наименьшем m значение отношения  достигает 4?
Примечание: 8 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.
Решение
Привожу решения Сергея Половинкина, Олега Полубасова и Анатолия Казмерчука.
Обсуждение
Трудная дистанция утомила марафонцев. На ММ200 было прислано наименьшее в 20-м туре число ответов. Тем удивительнее, что именно побила рекорд Марафона по разнообразию: пять присланных и один авторский ответ оказались попарно различны! (Точнее, наименьшие искомые n у меня и Олега совпали, но при разных триангуляциях и разных T(n)).
Наименьшие найденные участниками значения n, начиная с которых  достигает 4, оказались равными 20, 18, 15, 14 и, наконец, 12.
Трудность задачи в том, что ряд T(n) не получается путем добавления на каждом шаге новой прямой к предыдущей конфигурации, а строится значительно сложнее.
Ясно, конфигурация тем лучше, чем больше точек пересечения образуют рассекающие прямые внутри (в крайнем случае на границе) треугольника. Для этого надо избегать параллельности рассекающих прямых, их пресечения вне треугольника, пересечения многих прямых в одной точке. (Менее понятно лишь, как совместить это с сохранением треугольности всех фигур разбиения.)
С этих позиций преимущества решения Анатолия видны сразу. Только ему удалось избежать параллельности рассекающих прямых, и только у него ни в одной точке не пересекаются более трех рассекающих прямых.
Удивление, граничащее с шоком, вызвал у меня тот факт, что я (а судя по присланным решениям, не только я) не смог найти в сети задач, в которых возникает последовательность T(n).
Естественность постановки задачи вступает в явное противоречие с ее нераскрученностью.
Награды
При распределении призовых баллов учтено, что только у Анатолия Казмерчука присутствует обоснование оптимальности решения. (Впрочем, было бы странно, если бы в других решениях была обоснована их оптимальность.)
За решение задачи ММ200 участники получают следующие призовые баллы:
Анатолий Казмерчук - 14;
Олег Полубасов - 10;
Виктор Филимоненков - 7;
Сергей Половинкин - 6;
Ариадна - 5.
Эстетическая оценка задачи - 4.6 балла
 



[img]/modules/file/icons/application-octet-stream.png[/img] 200.rar