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

[VAL]

maxal в сообщении #823526 писал(а):

Надо бы заменить в примерах/комментариях в A231085 все знаки "<=" на "<", а в A231074 наоборот - все "<" на "<=".

В A231074 заменил.
А в A231085 менять не стал (заменил только в одном месте слово "nondecreasing" на "increasing"). Там где в комментах стоят знаки "<=", они уместны.

-- 07 фев 2014, 08:58 --

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

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

В подобных ситуациях я иногда (не добавляя пока новый элемент в саму последовательность) писал в комментариях что-то типа: возможно следующий член равен тому-то (в нашем случае, a(7)=4676).

Вроде бы, модераторы не возражали.

Пока писал этот комментарий, получил уведомление от OEIS. Но, насколько я понял, 4676 появился только в дискуссии, но не в тексте статьи.

[Masik]

Цитата:

ММ191 (4 балла)
Рассматриваются тройки чисел $a \le b \le c$, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

Числа из какого кольца или поля рассматриваются? Если целые, то на каждую подходящую тройку чисел найдётся соответствующая тройка отрицательных чисел. Если действительные, то что значит "больше"?

[VAL]

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

Цитата:

ММ191 (4 балла)
Рассматриваются тройки чисел $a \le b \le c$, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

Числа из какого кольца или поля рассматриваются? Если целые, то на каждую подходящую тройку чисел найдётся соответствующая тройка отрицательных чисел.

Разумеется!

Цитата:

Если действительные, то что значит "больше"?

Не знаю.

И, стало быть, числа числа натуральные.

[green_orange]

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

Примечание:
13 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.

А это примечание к какой задаче относится? Про 13 баллов там нигде не было.

[VAL]

green_orange в сообщении #868285 писал(а):

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

Примечание:
13 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.

А это примечание к какой задаче относится?

К ММ200.

Цитата:

Про 13 баллов там нигде не было.

Было. Но не в окончательной редакции.

В более раннем варианте ММ200 был еще один пункт, но затем условие подверглось секвестированию.

[fiviol]

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

Цитата:

ММ191 (4 балла)
Рассматриваются тройки чисел $a \le b \le c$, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

Числа из какого кольца или поля рассматриваются? Если целые, то на каждую подходящую тройку чисел найдётся соответствующая тройка отрицательных чисел. Если действительные, то что значит "больше"?

Утверждение "на каждую подходящую тройку чисел найдётся соответствующая тройка отрицательных чисел" годится и для действительных чисел. А вопрос "что значит "больше" - и для целых. :)

[green_orange]

По MM199:
Количество углов у многоугольника ненулевого рода - это количество углов внешнего многоугольника или оно плюс сумма количеств углов внутренних?

[VAL]

green_orange в сообщении #868738 писал(а):

По MM199:
Количество углов у многоугольника ненулевого рода - это количество углов внешнего многоугольника или оно плюс сумма количеств углов внутренних?

Второе.

[VAL]

Напоминаю, что сегодня последний день приема решений ММ191.
Еще можно успеть на уходящий поезд.

[VAL]

===========ММ191===============

ММ191 (4 балла)

Рассматриваются тройки чисел $a \le b \le c$, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

Решение

Для каждого фиксированного значения $c$ зададим преобразование множества троек по правилу: $(a,b,c)$ переходит в $(c+1-b,c+1-a,c)$. При этом тройки, не образующие треугольник перейдут в тройки, образующие треугольник, а обратное не всегда верно. Поэтому троек, образующих треугольник, больше.

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

(Решение Константина Хадаева)

MM191
Рассмотрим преобразование $(a,b,c)\to(c-b,c-a,c)$. Оно переводит допустимые тройки в допустимые, кроме случая $c=b$. Если из первой тройки можно было собрать треугольник, то $a+b>c, (c-a)+(c-b)<c$. И наоборот, если в первой тройке меньше, то во второй больше. все случаи, кроме $b=c$ и $a+b=c$ разбились на пары, в которых ровно из одной тройки получается треугольник.
В случае $b=c$ треугольник всегда строится. Этих случаев $n+(n-1)+\ldots+1=\frac{n(n+1)}{2}$.
В случае $a+b=c$ треугольник всегда не строится. Для каждого $c$ есть $\lfloor\frac{c}{2}\rfloor$ пар. Если $n$ чётно, то всего их $n/2+(n-2)/2+(n-2)/2+\ldots+1+1=\frac{n}{2}+\frac{n(\frac{n}{2}-1)}{2}=\frac{n^2}{4}$. Если $n$ нечётно, то их $(n-1)/2+(n-1)/+\ldots+1+1=\frac{n^2-1}{4}$.
$\frac{n^2-1}{4}<\frac{n^2}{4}<\frac{n(n+1)}{2}$ при всех натуральных $n$, поэтому больше тех троек, из которых можно составить треугольник.

Вложение:

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

Вложение:

Комментарий к файлу: Решение Сергея Половинкина
mm191_Polovinkin.pdf [80.12 Кб]
Скачиваний: 536

Вложение:

Комментарий к файлу: Решение Ариадны
191_Ariadna.doc [691.5 Кб]
Скачиваний: 557

Обсуждение

Эта задача привлекла меня двумя моментами:
наличием простого изящного решения;
любопытным совпанением чисел $T(c)$ и $N(c+1)$, где $T(c)$ и $N(c)$ количества троек с фиксированным, соответственно образующих и не образующих треугольник.

Участники порадовали разнообразием решений.
Решения Олега Полубасова и Анатолия Казмерчука идентичны авторскому. Решения Константина Хадаева и Виктора Филимоненкова основаны на той же идее, но в несколько иной редакции.
Другие участники посчитали количества подходящих и неподходящих троек для каждого фиксированного $c$ (иногда этот подсчет был оформлен в виде шага индукции) или для всех троек, у которых большая сторона не превосходит $c$.
В результате некоторые решения растянулись до шести полновесных страниц
Очень наглядное решение визуальное решение предложил Дмитрий Пашуткин (то, что при этом он перепутал цвета, я списал на проблемы с цветовосприятием )
mm_191.jpg

Антон Никонов заметил, что последовательность $T(c)$ (а следовательно и $N(c)$) есть в OEIS - A002623.

Награды

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

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

[kknop]

Цитата:

Эта задача привлекла меня двумя моментами:

Нас не обманешь. Она Вас привлекла потому, что дала повод задать ММ192-ю.

Deggial: пользуйтесь тегом quote!

[Masik]

kknop в сообщении #907444 писал(а):

Цитата:

Эта задача привлекла меня двумя моментами:

Нас не обманешь. Она Вас привлекла потому, что дала повод задать ММ192-ю.

Нет, Константин. Эта задача интересна и сама по себе. Обычно все эти целочисленные треугольники дают очень рваный график, а тут всё ровненько, совершенно неожиданно.

[VAL]

kknop в сообщении #907444 писал(а):

Цитата:

Эта задача привлекла меня двумя моментами:

Нас не обманешь. Она Вас привлекла потому, что дала повод задать ММ192-ю.

Я не лукавил.
Ну ладно,.. тремя моментами

[VAL]

===========ММ192===============

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

Рассматриваются целочисленные треугольники со сторонами, не превосходящими данного натурального числа n.
Каких треугольников больше: остроугольных или тупоугольных?

Решение

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

Вложение:

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

Вложение:

Комментарий к файлу: Решение Дмитрия Пашуткина
MM192_Pashutkin.pdf [133.69 Кб]
Скачиваний: 587

Вложение:

Комментарий к файлу: Решение Ариадны
MM192_Ariadna.doc [1.49 Мб]
Скачиваний: 565

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

MM192
Если $n>38$, тогда тупо: угольных

Зависимость разности($raz$) между количеством тупоугольных и остроугольных от $n$ можно вычислить по формуле:

$$raz(n) = \sum_{c=1}^n \left( k(k + \frac{1+(-1)^c}2) - c + \sum_{s=\lfloor-\frac32c\rfloor + 5k + 4 + (-1) ^ c}^{c-5} \lfloor y - c\rfloor + \frac{(-1) ^ {\lfloor y \rfloor}-1}2-\lfloor 1 - y + \lfloor y \rfloor\rfloor\right)$$

, где

$$k =\lfloor\frac{2c(\sqrt{2} - 1) + 1-(-1)^c}4\rfloor $$

$$y = \frac{2\sqrt{9c^2 - 8sc - s^2}}5$$

Шаг увеличения $s$ равен $5$.

А вот и табличка для первых 50-ти членов последовательности:

\begin{array}{rr} n & raz(n)\\ \\ 1 & -1\\ 2 & -3\\ 3 & -5\\ 4 & -9\\ 5 & -13\\ 6 & -17\\ 7 & -23\\ 8 & -29\\ 9 & -34\\ 10 & -39\\ 11 & -45\\ 12 & -53\\ 13 & -59\\ 14 & -65\\ 15 & -70\\ 16 & -76\\ 17 & -82\\ 18 & -88\\ 19 & -92\\ 20 & -95\\ 21 & -100\\ 22 & -102\\ 23 & -104\\ 24 & -108\\ 25 & -109\\ \end{array}

\begin{array}{rr} 26 & -108\\ 27 & -104\\ 28 & -102\\ 29 & -100\\ 30 & -95\\ 31 & -91\\ 32 & -83\\ 33 & -74\\ 34 & -63\\ 35 & -48\\ 36 & -36\\ 37 & -20\\ 38 & -6\\ 39 & 15\\ 40 & 38\\ 41 & 58\\ 42 & 82\\ 43 & 108\\ 44 & 140\\ 45 & 174\\ 46 & 206\\ 47 & 242\\ 48 & 278\\ 49 & 319\\ 50 & 363\\ \end{array}

Из формулы следует, что перевес тупоугольных будет неуклонно возрастать при дальнейшем увеличении $n$.

Обсуждение

В данной задаче меня привлекло то, что перевес тупоугольных наступает при достаточно большом $n$. И это притом, что в пределе этот перевес довольно значителен (в пределе примерно $1.33:1$).

Задача ММ192 оказалась труднее предыдущей. Это выразилось в меньшем числе ответов при одновременном увеличении числа ошибок.

Часть ошибок связана неверным определением $n$, при котором тупоугольных треугольников становится больше. Это связано с "погореловской" трактовкой треугольников, когда тройки $(2,3,4,)$ и $(3,2,4)$ определяют разные треугольники. Сторонники этой версии даже нашли ей подтверждение в виде последовательности A006003. При этом их не смутило ни то, что среди многочисленных интерпретаций этой последовательности не упоминаются целочисленные треугольники, ни то, что в обсуждении прошлой задачи явно указана совсем другая последовательность (A002623), отвечающая за за количество целочисленных треугольников.

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

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

Особняком стоит решение Константина Хадаева. Применив тот же подход, что большинство остальных участников, Константин перепутал области, отвечающие за остроугольные и тупоугольные треугольники. Я бы не стал столь жестко снижать баллы за такую ошибку, если не два обстоятельства:
1. На мой взгляд, слишком самонадеянно не проверить свое решение хотя бы на простейших частных случаях. В данном случае достаточно было взять $n=1$, чтобы понять, что в решении что-то не так, если единственный для этого случая равносторонний треугольник превратился в тупоугольный.
2. Как я это обычно делаю в ситуации, когда решение прислано загодя и ошибка имеет характер "с точностью до наоборот", я намекал Константину на его ошибку. Но безрезультатно.

Вслед за Константином Хадаевым (но с другим результатом) я подсчитал "средний больший угол" в треугольнике (или больший угол в "среднем" треугольнике). У меня получилось примерно $94^014'$.

Награды

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

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

[Yadryara]

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

Надеюсь, что Антон Никонов дополнит соответствующие статьи явными формулами.
Почему именно Антон? Потому что только он нашел соответствующие явные формулы.

Прошу Вас побыстрее сообщить, какие именно формулы нужны. Ибо с момента их вывода прошло уже два месяца и восстановить ход решения мне сейчас затруднительно. А позже будет ещё сложнее.

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

Безусловно этот подвиг (см. формулы в решении Антона) заслуживает отдельных призовых баллов.

Насчёт подвига — это, видимо, алаверды на моё прошлогоднее :

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

Олимпийский марафон стартовал в Марафоне. Известный волгоградец Владимир Лецко, тоже специализируется в Марафоне. Математическом.
Именно специализируется. Без кавычек. Проводить его столько лет — это своеобразный подвиг. Сожалею, что я узнал о нём только в этом году.

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

Я их и добавил. Но при этом вычел такое число баллов за традиционное нежелание приводить пояснения и обоснования.

Видимо, пропущено "же". Такое же. Миллиард начислил, биллион вычел

Откуда же я знал, что явная формула будет только у меня? Полагал, что будут решения получше. Кому охота разбираться в длинном и, что важнее, не самом лучшем решении. Вот и избавил Вас от него

Мне, например, не нравится, что шаг $s$ равен 5-ти, а не единице. Одна попытка перенормировать мне не понравилась, а другие я не удосужился осуществить.

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

Мне помогали навыки любителя головоломок и программиста-прикладника. "А попробую-ка я так", "а зайду-ка я с этой стороны". Моя любимая эвристика. Помнится, смотрел на диапазоны возможных значений $a$ и $b$, и кое-что понял...

А вдруг у меня ноу-хау есть