2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 58  След.
 
 Re: Обсуждение и разбор марафонских задач
Сообщение07.02.2014, 08:43 
Заслуженный участник


27/06/08
4058
Волгоград
maxal в сообщении #823526 писал(а):
Надо бы заменить в примерах/комментариях в A231085 все знаки "<=" на "<", а в A231074 наоборот - все "<" на "<=".
В A231074 заменил.
А в A231085 менять не стал (заменил только в одном месте слово "nondecreasing" на "increasing"). Там где в комментах стоят знаки "<=", они уместны.

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

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

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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение26.05.2014, 21:12 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение26.05.2014, 22:52 
Заслуженный участник


27/06/08
4058
Волгоград
Masik в сообщении #868141 писал(а):
Цитата:
ММ191 (4 балла)
Рассматриваются тройки чисел $a \le b \le c$, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение27.05.2014, 07:25 


18/12/13
30
Новосибирск
VAL в сообщении #868000 писал(а):
Примечание:
13 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.
А это примечание к какой задаче относится? Про 13 баллов там нигде не было.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение27.05.2014, 08:06 
Заслуженный участник


27/06/08
4058
Волгоград
green_orange в сообщении #868285 писал(а):
VAL в сообщении #868000 писал(а):
Примечание:
13 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.
А это примечание к какой задаче относится?
К ММ200.
Цитата:
Про 13 баллов там нигде не было.
Было. Но не в окончательной редакции.

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение27.05.2014, 15:12 


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

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


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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение28.05.2014, 11:36 


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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение28.05.2014, 12:21 
Заслуженный участник


27/06/08
4058
Волгоград
green_orange в сообщении #868738 писал(а):
По MM199:
Количество углов у многоугольника ненулевого рода - это количество углов внешнего многоугольника или оно плюс сумма количеств углов внутренних?
Второе.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение12.09.2014, 07:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение13.09.2014, 09:04 
Заслуженный участник


27/06/08
4058
Волгоград
===========ММ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 Кб]
Скачиваний: 369
Вложение:
Комментарий к файлу: Решение Сергея Половинкина
mm191_Polovinkin.pdf [80.12 Кб]
Скачиваний: 335
Вложение:
Комментарий к файлу: Решение Ариадны
191_Ariadna.doc [691.5 Кб]
Скачиваний: 362


Обсуждение

Эта задача привлекла меня двумя моментами:
наличием простого изящного решения;
любопытным совпанением чисел $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 балла

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение13.09.2014, 21:31 


05/08/08
55
Санкт-Петербург
Цитата:
Эта задача привлекла меня двумя моментами:


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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.09.2014, 06:02 
Аватара пользователя


08/12/11
110
СПб
kknop в сообщении #907444 писал(а):
Цитата:
Эта задача привлекла меня двумя моментами:

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

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.09.2014, 20:17 
Заслуженный участник


27/06/08
4058
Волгоград
kknop в сообщении #907444 писал(а):
Цитата:
Эта задача привлекла меня двумя моментами:

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

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение20.09.2014, 11:11 
Заслуженный участник


27/06/08
4058
Волгоград
===========ММ192===============

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

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

Решение

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

Вложение:
Комментарий к файлу: Решение Олега Полубасова
MM192_Полубасов.pdf [380.72 Кб]
Скачиваний: 355
Вложение:
Комментарий к файлу: Решение Дмитрия Пашуткина
MM192_Pashutkin.pdf [133.69 Кб]
Скачиваний: 386
Вложение:
Комментарий к файлу: Решение Ариадны
MM192_Ariadna.doc [1.49 Мб]
Скачиваний: 367


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

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 балла

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение21.09.2014, 05:41 
Аватара пользователя


29/04/13
7134
Богородский
VAL в сообщении #909787 писал(а):
Надеюсь, что Антон Никонов дополнит соответствующие статьи явными формулами.
Почему именно Антон? Потому что только он нашел соответствующие явные формулы.

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

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

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

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


VAL в сообщении #909787 писал(а):
Я их и добавил. Но при этом вычел такое число баллов за традиционное нежелание приводить пояснения и обоснования.

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

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

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 861 ]  На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 58  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group