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

[Yadryara]

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

Даже обидно, что таинство пропало

Да и бог с ним. Хватит ещё на наш век таинств. У меня в темах, например, они тоже есть

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

Так, как насчет размещения формул в OEIS?

Можете посмотреть, я направил одну для остроугольных в A247588 ещё 3 дня назад. Пока молчат.

[VAL]

===========ММ193===============

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

Игроки Вася, Федя и Коля сыграли несколько паркий в настольный теннис навылет. Сколько партий мог сыграть Коля, если Вася сыграл a партий, а Федя - b?

Примечания:
участники первой партии определяются жребием;
для определенности будем считать, что $b \le a$.

Решение

Приведу решения Ариадны, Олега Полубасова и Анатолия Казмерчука.

Вложение:

Комментарий к файлу: Решение Ариадны
193_Ариадна.pdf [642.16 Кб]
Скачиваний: 695

Вложение:

Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_193.docx [30.86 Кб]
Скачиваний: 756

Вложение:

Комментарий к файлу: Решение Олега Полубасова
MM193_Полубасов.pdf [335.84 Кб]
Скачиваний: 673

Обсуждение

Задача ММ193 привлекла меня тем, что оказалась сложнее, чем я ожидал, придумав условие.

Другой особенностью оказалось разнообразие ответов. Среди присланных девяти (плос мой собственный) совпадают всего 2. Притом что безоговорочно правильными являются восемь.
Вот несколько примеров из неопубликованных решений:

Yadryara писал(а):

Коля мог сыграть любое количество партий с шагом $2$
от $a-b+2\lfloor{\frac{2b+1-a}3}\rfloor$
до $3b-a+2\lfloor{\frac{a}{b+1}\rfloor$
включительно.

fiviol писал(а):

Коля мог сыграть $a+b-2y$ партий, где $y$ - любое целое число, лежащее в интервале:
$\max(0; a-b-1) \le y \le \frac{a+b+1}3$

ПСВ писал(а):

$c$ может принимать любые значения с шагом 2 от $2\lceil\frac{2b-a-1}3+a-b$ до $2b-a-|a-b-1|+1$

val-etc писал(а):

$c_{min}=\frac s3$, где $s$ равно $a+b$, округленному ближайшего кратного 3 одной четности с $a+b$.
$c_{max}=3b-a+2sign(a-b)$.
Допустимые значения c изменяются от $c_{min}$ до $c_{max}$ по числам одной четности с $a+b$.

Равносильность ответов (надеюсь, что она таки имеется) совсем не очевидна. И это при том, что я привел только наиболее короткие варианты

Еще один момент - строгость обоснований того факта, что все промежуточные значения подходящей четности достижимы. Одни участники потратили на это достаточно много усилий, другие сочли это очевидным, а один пообещал обосновать этот момент, не обещание не выполнил
Лично мне представляется, что это почти очевидно, но... на итоговое оценки этот момент, все же, повлиял.

Наличие дополнительного параметра $k$ в ответе Олега Полубасова, представляется мне излишеством. На мой взгляд, не только две игры, но и одна, это вполне себе "несколько".

Награды

В зависимости от степени строгости обоснования и наличия/отсутствия обобщений и неточностей за решения задачи ММ193 начислены следующие баллы: Виктор Филимоненков, Ариадна, Владимир Дорофеев, Олег Полубасов, Дмитрий Пашуткин и Анатолий Казмерчук - по 6 баллов; Антон Никонов и Сергей Половинкин - по 5 баллов; Константин Хадаев - 4 призовых балла.

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

[VAL]

Цитата:

Вложение:
Комментарий к файлу: Решение Ариадны
193_Ариадна.pdf [642.16 Кб]
Скачиваний: 14
Вложение:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_193.docx [30.86 Кб]
Скачиваний: 2
Вложение:
Комментарий к файлу: Решение Олега Полубасова
MM193_Полубасов.pdf [335.84 Кб]
Скачиваний: 3

Интересно, это ник так завораживает?

[Masik]

(Оффтоп)

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

Цитата:

Вложение:
Комментарий к файлу: Решение Ариадны
193_Ариадна.pdf [642.16 Кб]
Скачиваний: 14
Вложение:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_193.docx [30.86 Кб]
Скачиваний: 2
Вложение:
Комментарий к файлу: Решение Олега Полубасова
MM193_Полубасов.pdf [335.84 Кб]
Скачиваний: 3

Интересно, это ник так завораживает?

Ариадна - это та, которая обещала Тесею, но изменила ему с Дионисом? Тогда ничего удивительного, математики любят изменчивость.

А почему Антону Никонову не добавили обещанный ему миллиард? Он ведь, вроде бы, что-то там обосновал.

[Yadryara]

Да нет, ничего не обосновывал. Так, голые формулы.

Считайте, что я как "ABBA" — от миллиарда отказался

[Masik]

Yadryara в сообщении #913479 писал(а):

Да нет, ничего не обосновывал. Так, голые формулы.
Считайте, что я как "ABBA" — от миллиарда отказался

Понимаете, Антон, "отказался - не отказался" влияет только на суммарное число баллов, которое, вообще, ничего не значит, это всё майя. Если я правильно понял политику ведущего, то начисленные за решение задачи баллы - это всего лишь способ сообщить участникам: "Сюда не ходи, туда ходи". Пошёл в правильную сторону - надо поощрять.
С уважением, Олег Полубасов. СПб.

[VAL]

Yadryara в сообщении #911838 писал(а):

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

Так, как насчет размещения формул в OEIS?

Можете посмотреть, я направил одну для остроугольных в A247588 ещё 3 дня назад. Пока молчат.

Предлагаю:
1. Поправить формулу, заменив на такую
A247588(n) = Sum (j=1 .. n(1 - sqrt(2)/2), n - j - floor(sqrt(2jn - j^2)))
2. С учетом исправлений распространить на другие последовательности.

-- 29 сен 2014, 08:41 --

(Оффтоп)

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

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

Цитата:

Вложение:
Комментарий к файлу: Решение Ариадны
193_Ариадна.pdf [642.16 Кб]
Скачиваний: 14
Вложение:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_193.docx [30.86 Кб]
Скачиваний: 2
Вложение:
Комментарий к файлу: Решение Олега Полубасова
MM193_Полубасов.pdf [335.84 Кб]
Скачиваний: 3

Интересно, это ник так завораживает?

Ариадна - это та, которая обещала Тесею, но изменила ему с Дионисом? Тогда ничего удивительного, математики любят изменчивость.

То есть, дело таки в нике.

Цитата:

А почему Антону Никонову не добавили обещанный ему миллиард? Он ведь, вроде бы, что-то там обосновал.

По пунктам:
1. Миллиарда никто не обещал. Да и нет у меня миллиарда. Я ведь не олигарх.
2. Обоснований не было. Были формулы для остро(тупо, прямо)угольных треугольников. Правда, из них (особенно из последней) ясно откуда они (а следовательно и формула для ММ192) взялись. Но обоснований таки не было.
3(главное). Привожу выдержку из правил:

Цитата:

Решение каждой задачи оценивается из указанного в задаче количества баллов, начисляемых за полное, правильное и своевременное решение. Если решение не обладает всеми вышеперечисленными признаками (но прислано в срок), за него все равно можно получить часть призовых баллов. Авторы оригинальных, неизвестных ведущему, решений могут поощряться дополнительными баллами. Субъективизм в оценивании является неизбежным злом. Свои претензии вы можете присылать ведущему. Если он сочтет их обоснованными, оценка может быть пересмотрена.

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

[Yadryara]

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

Предлагаю:
1. Поправить формулу, заменив на такую
A247588(n) = Sum (j=1 .. n(1 - sqrt(2)/2), n - j - floor(sqrt(2jn - j^2)))

Я всё же настаиваю, что суммирование должно начинаться с $j=0$. А в остальном согласен. Уже добавил в дискуссию.

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

2. С учетом исправлений распространить на другие последовательности.

То есть не дожидаясь, пока эту одобрят? Хорошо, попробую.

[VAL]

Yadryara в сообщении #913551 писал(а):

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

Предлагаю:
1. Поправить формулу, заменив на такую
A247588(n) = Sum (j=1 .. n(1 - sqrt(2)/2), n - j - floor(sqrt(2jn - j^2)))

Я всё же настаиваю, что суммирование должно начинаться с $j=0$. А в остальном согласен. Уже добавил в дискуссию.

Да, конечно с 0. Я про остальное. А это просто моя извечная неаккуратность.

[VAL]

Как это у меня бывает, формулировка ММ197 получилась, мягко говоря, невнятной

Надеюсь, что уточненная формулировка устранит возможные кривотолки.

Цитата:

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

Будем говорить, что n-угольник относится к классу k, если его можно разрезать на k треугольников одной прямой и нельзя разрезать одной прямой на большее число треугольников. Найти все возможные значения k для $n = 2014$.

Примечания:
1. Никаких других фигур при разрезании возникать не должно.
2. Если вышеописанный разрез осуществить нельзя, многоугольник относится к классу 0.

[fiviol]

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

Как это у меня бывает, формулировка ММ197 получилась, мягко говоря, невнятным

Надеюсь, что уточненная формулировка устранит возможные кривотолки.

Цитата:

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

Будем говорить, что n-угольник относится к классу k, если его можно разрезать на k треугольников одной прямой и нельзя разрезать одной прямой на большее число треугольников. Найти все возможные значения k для $n = 2014$.

Примечания:
1. Никаких других фигур при разрезании возникать не должно.
2. Если вышеописанный разрез осуществить нельзя, многоугольник относится к классу 0.

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

[VAL]

fiviol в сообщении #914932 писал(а):

Мне первоначальная формулировка больше нравится. Что невнятного в том, что некоторые многоугольники принадлежат одновременно к нескольким классам, а некоторые - к никакому классу?

Ну, в этом случае их, как минимум, не следует называть классами. Все же классы намекают на классификацию.

Цитата:

А с уточнениями, вообще-то, меняется задача, которую кто-то уже решил: теперь надо еще доказывать, что на большее количество треугольников приведенные примеры не могут быть разбиты.

Это настолько очевидно, что мне бы и в голову не пришло, что это надо доказывать.
(Но задача, конечно же, меняется. Хотя бы в силу того, что ответ очевидным образом меняется.)

[VAL]

===========ММ194===============

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

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

Решение

Приведу решения Антона Никонова, Сергея Половинкина (в отдельном письме чуть позже), а также (куда же без них?) Ариадны и Олега Полубасова.

(Решение Антона Никонова)

Yadryara писал(а):

Я тут подумал: а что, если решить задачу в лоб. То есть попросту разобрать все возможные случаи при $n<8$.

Поскольку их не так много, всего $C_6^2 \cdot C_4^3=15\cdot4=60$ вариантов.

Если $x$ — минимальная сторона, то стороны одного треугольника $x,x+a,x+b$, а другого $x+c,x+d,x+f$.

Из формулы Герона следует, что площади этих тр-ков равны в том и только том случае, если:

$(3x+c+d+f)(x+d+f-c)(x+c+f-d)(x+c+d-f) = (3x+a+b)(x+a+b)(x+b-a)(x+a-b)$

Преобразование этого уравнения даёт, не побоюсь этого слова, кубический четырёхчлен:

$$k3x^3 + k2x^2 + k1x + k0 = 0$$

, где

$k3=4(c+d+f-a-b)$

$k2=2(-4ab+a^2+b^2-c^2+4cd+4cf-d^2+4df-f^2)$

$k1=4(-a^2b+a^3-ab^2+b^3-c^3+c^2d+c^2f+cd^2+cf^2-d^3+d^2f+df^2-f^3)$

$k0=a^4 - 2a^2b^2 + b^4 - c^4 + 2c^2d^2 + 2c^2f^2 - d^4 + 2d^2f^2 - f^4$


Интерес представляют натуральные корни этого монстра. Не забывая про Кардано, посмотрим более пристально, есть ли они у него:

\begin{array}{rrrrrrrrrr} a & b & c & d & f & k3 & k2 & k1 & k0 & \text{Положительные корни}\\ \\ 1 & 2 & 3 & 4 & 5 & 36 & 270 & 684 & 585 & \text {Нет}\\ 1 & 2 & 3 & 4 & 6 & 40 & 304 & 728 & 464 & \text {Нет}\\ 1 & 2 & 3 & 5 & 6 & 44 & 358 & 988 & 905 & \text {Нет}\\ 1 & 2 & 4 & 5 & 6 & 48 & 432 & 1392 & 1584 & \text {Нет}\\ 1 & 3 & 2 & 4 & 5 & 28 & 210 & 468 & 295 & \text {Нет}\\ 1 & 3 & 2 & 4 & 6 & 32 & 236 & 448 & 64 & \text {Нет}\\ 1 & 3 & 2 & 5 & 6 & 36 & 282 & 652 & 415 & \text {Нет}\\ 1 & 3 & 4 & 5 & 6 & 44 & 434 & 1444 & 1639 & \text {Нет}\\ 1 & 4 & 2 & 3 & 5 & 20 & 174 & 420 & 225 & \text {Нет}\\ 1 & 4 & 2 & 3 & 6 & 24 & 192 & 328 & -160 & 0.393\\ 1 & 4 & 2 & 5 & 6 & 32 & 288 & 768 & 576 & \text {Нет}\\ 1 & 4 & 3 & 5 & 6 & 36 & 366 & 1156 & 1121 & \text {Нет}\\ 1 & 5 & 2 & 3 & 4 & 12 & 162 & 636 & 711 & \text {Нет}\\ 1 & 5 & 2 & 3 & 6 & 20 & 202 & 532 & 191 & \text {Нет}\\ 1 & 5 & 2 & 4 & 6 & 24 & 252 & 768 & 576 & \text {Нет}\\ 1 & 5 & 3 & 4 & 6 & 28 & 322 & 1100 & 1031 & \text {Нет}\\ 1 & 6 & 2 & 3 & 4 & 8 & 176 & 952 & 1360 & \text {Нет}\\ 1 & 6 & 2 & 3 & 5 & 12 & 198 & 940 & 1225 & \text {Нет}\\ 1 & 6 & 2 & 4 & 5 & 16 & 240 & 1104 & 1456 & \text {Нет}\\ 1 & 6 & 3 & 4 & 5 & 20 & 302 & 1372 & 1801 & \text {Нет}\\ 2 & 3 & 1 & 4 & 5 & 20 & 126 & 180 & 25 & \text {Нет}\\ 2 & 3 & 1 & 4 & 6 & 24 & 144 & 104 & -272 & 1.\text { Вырожд. } S = 0.\\ 2 & 3 & 1 & 5 & 6 & 28 & 182 & 260 & 25 & \text {Нет}\\ 2 & 3 & 4 & 5 & 6 & 40 & 416 & 1400 & 1600 & \text {Нет}\\ 2 & 4 & 1 & 3 & 5 & 12 & 90 & 132 & -45 & 0.284\\ 2 & 4 & 1 & 3 & 6 & 16 & 100 & -16 & -496 & 2.\text { Вырожд. }S = 0.\\ 2 & 4 & 1 & 5 & 6 & 24 & 180 & 336 & 144 & \text {Нет}\\ 2 & 4 & 3 & 5 & 6 & 32 & 340 & 1072 & 1040 & \text {Нет}\\ 2 & 5 & 1 & 3 & 4 & 4 & 78 & 348 & 441 & \text {Нет}\\ 2 & 5 & 1 & 3 & 6 & 12 & 102 & 140 & -199 & 0.847\\ 2 & 5 & 1 & 4 & 6 & 16 & 144 & 336 & 144 & \text {Нет}\\ 2 & 5 & 3 & 4 & 6 & 24 & 288 & 968 & 896 & \text {Нет}\\ \end{array}


\begin{array}{rrrrrrrrrr} a & b & c & d & f & k3 & k2 & k1 & k0 & \text{Положительные корни}\\ \\ 2 & 6 & 1 & 3 & 4 & 0 & 84 & 608 & 1024 & \text {Нет}\\ 2 & 6 & 1 & 3 & 5 & 4 & 98 & 548 & 835 & \text {Нет}\\ 2 & 6 & 1 & 4 & 5 & 8 & 132 & 672 & 1024 & \text {Нет}\\ 2 & 6 & 3 & 4 & 5 & 16 & 260 & 1184 & 1600 & \text {Нет}\\ 3 & 4 & 1 & 2 & 5 & 4 & 30 & -84 & -335 & 3.805\\ 3 & 4 & 1 & 2 & 6 & 8 & 32 & -296 & -896 & 5.772\\ 3 & 4 & 1 & 5 & 6 & 20 & 158 & 268 & 49 & \text {Нет}\\ 3 & 4 & 2 & 5 & 6 & 24 & 240 & 616 & 400 & \text {Нет}\\ 3 & 5 & 1 & 2 & 4 & -4 & 18 & 132 & 151 & 8.759\\ 3 & 5 & 1 & 2 & 6 & 4 & 26 & -196 & -689 & 6.116\\ 3 & 5 & 1 & 4 & 6 & 12 & 114 & 212 & -41 & 0.176\\ 3 & 5 & 2 & 4 & 6 & 16 & 188 & 512 & 256 & \text {Нет}\\ 3 & 6 & 1 & 2 & 4 & -8 & 16 & 328 & 624 & 8.179\\ 3 & 6 & 1 & 2 & 5 & -4 & 22 & 212 & 345 & 11.020\\ 3 & 6 & 1 & 4 & 5 & 4 & 94 & 484 & 729 & \text {Нет}\\ 3 & 6 & 2 & 4 & 5 & 8 & 160 & 728 & 960 & \text {Нет}\\ 4 & 5 & 1 & 2 & 3 & -12 & -18 & 84 & 81 & 2.460\\ 4 & 5 & 1 & 2 & 6 & 0 & 0 & -288 & -864 & \text {Нет}\\ 4 & 5 & 1 & 3 & 6 & 4 & 46 & -76 & -559 & 3.718\\ 4 & 5 & 2 & 3 & 6 & 8 & 112 & 184 & -304 & 1.\text { Вырожд. } S = 0.\\ 4 & 6 & 1 & 2 & 3 & -16 & -28 & 208 & 400 & 3.663\\ 4 & 6 & 1 & 2 & 5 & -8 & -12 & 48 & 16 & 2.\text { Вырожд. }S = 0.\\ 4 & 6 & 1 & 3 & 5 & -4 & 26 & 196 & 211 & 11.265\\ 4 & 6 & 2 & 3 & 5 & 0 & 84 & 400 & 400 & \text {Нет}\\ 5 & 6 & 1 & 2 & 3 & -20 & -58 & 92 & 121 & 1.740\\ 5 & 6 & 1 & 2 & 4 & -16 & -48 & 48 & 16 & 1.\text { Вырожд. } S = 0.\\ 5 & 6 & 1 & 3 & 4 & -12 & -18 & 140 & 121 & 3.175\\ 5 & 6 & 2 & 3 & 4 & -8 & 32 & 296 & 256 & 8.685\\ \end{array}

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

А вот и примеры решений:

\begin{array}{rrrrrrrrrr} a & b & c & d & f & k3 & k2 & k1 & k0 & \text{Положительные корни}\\ \\ 5 & 7 & 1 & 2 & 3 & -24 & -72 & 240 & 576 & 3\\ 9 & 10 & 1 & 6 & 8 & -16 & -64 & 304 & -224 & 1.\text { Вырожд. } S = 0; \quad 2 \\ 9 & 10 & 2 & 3 & 4 & -40 & -208 & 328 & 496 & 2\\ \end{array}

Взяв значения из 1-й строки и вспомнив, что корень — это минимальная сторона, получаю и другие стороны этого же тр-ка: $3+5=8;3+7=10$
И стороны другого тр-ка: $3+1=4;3+2=5;3+3=6$

То есть, это то самое первое решение $3;8;10$ и $4;5;6$. Откуда $n = 8$, поскольку используются некоторые из $8$ чисел в диапазоне $3...10$.

Два других решения для $n = 11$:

$2;11;12$ и $3;8;10$

$2;11;12$ и $4;5;6$

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

Обсуждение

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

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   

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


Награды

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

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

[VAL]

Привожу решение Сергея Половинкина

Вложение:

Комментарий к файлу: Собственно решение
mm194__Polovinkin.pdf [94.57 Кб]
Скачиваний: 686

Вложение:

Комментарий к файлу: Приложение 1
r_7.xls [59.5 Кб]
Скачиваний: 675

Вложение:

Комментарий к файлу: Приложение 2
r_8.xls [82 Кб]
Скачиваний: 664

[Masik]

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

Как это у меня бывает, формулировка ММ197 получилась, мягко говоря, невнятным

А Вы в каком школе учили русского языка?