2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 36, 37, 38, 39, 40, 41, 42 ... 56  След.
 
 Re: Обсуждение и разбор марафонских задач
Сообщение15.10.2017, 17:55 
Аватара пользователя


08/12/11
110
СПб
А я-то ломал голову, в чём дело. Понятно, что субъективность оценок неизбежна, но если бы вместо мистических историй ведущий рассказывал, что именно ему так понравилось в том или ином решении, что он поощрил их разным числом баллов, то участники бы знали, куда стремиться. Например, приветствуется краткость или подробность решения, или ещё какие-нибудь предпочтения имеются.

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


06/07/11
5615
кран.набрать.грамота
Masik
Не помню точно, где именно, но где-то на видном месте (в правилах, может быть) было написано, что дополнительные баллы даются за предложенное обобщение задачи и решение обобщенной задачи.

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


27/06/08
3552
Волгоград
===========ММ227===============

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

Пусть $n = \prod_{i=1}^s p_i^{a_i}$ - каноническое разложение $n$. Обозначим через $sopf(n)$ число $p_1+p_2+...p_s$.
Назовем натуральное число $k$ слабым, если уравнение $x = k\cdot sopf(x)$ неразрешимо в натуральных числах, и сильным в противном случае.
Доказать, что сильных чисел бесконечно много.
Найти наименьшее слабое число.
Доказать, что слабых чисел бесконечно много.

Решение

Привожу решения Валентины Колыбасовой, Анатолия Казмерчука, Олега Полубасова и Тимофея Игнатьева.

(Решение Тимофея Игнатьева)

Если $k=p$, где $p$ - простое, то $x=p^2$, т.к. $\operatorname{sopf}(x)=p$. Поскольку простых чисел бесконечное количество, то и сильных $k$ тоже бесконечное число.

Если число $k=\prod\limits_{j=1}^r p_j^{\beta_j}$ ($\beta_j>0$) - сильное, то и все числа с тем же набором простых делителей $\{p_1, p_2,\ldots,p_r\}$ - сильные. Пусть для такого $k$ существует решение уравнения $x$. Тогда для $k'$ с тем же набором простых делителей, что и у $k$, $x'=\frac{xk'}{k}$ (т.к. $k$ - сильное, то $x$ делится на $k$) будет решением уравнения (из способа нахождения $x'$ видно, что у $x'$ и $x$ одинаковый набор простых делителей, поэтому $\operatorname{sopf}(x')=\operatorname{sopf}(x)$).
Очевидно, что аналогичное утверждение справедливо и для слабых чисел. Таким образом, если будет обнаружено хотя бы одно слабое число, то задача о доказательстве бесконечности множества слабых чисел будет решена (поскольку чисел с одинаковым набором простых делителей бесконечное количество).

Будем искать наименьшее слабое число в виде обыкновенного произведения различных простых чисел (исходя из выше написанного, для любого слабого $k$ с набором простых делителей $\{p_1, p_2,\ldots,p_r\}$ существует слабое число вида $\prod\limits_{j=1}^r p_j$, которое, очевидно, не больше $k$). Число такого вида будет сильным, если для него можно подобрать такие простые числа $\{p_{r+1}, p_{r+2},\ldots, p_s\}$, что $\sum\limits_{j=1}^n p_j=\sum\limits_{j=1}^r p_j+\sum\limits_{j=r+1}^s p_j=\prod\limits_{j=1}^s p_j^{\gamma_j}$ ($\gamma_j\ge 0$, $s\ge r$), и слабым в противном случае. Т.к. $p_j\ge 2$, то $\sum\limits_{j=1}^r p_j\ge\sum\limits_{j=r+1}^s p_j$, причем равенство достигается только в случае $s=r+1$, $p_1=2$, $p_s=\sum\limits_{j=1}^r p_j$. При $r=1$ число $k$ - сильное, поэтому в ходе перебора необходимо рассматривать наборы, состоящие по меньшей мере из 2 различных простых чисел.
Докажем, что число $46=2\cdot 23$ - наименьшее слабое число:
  1. Покажем, что это число действительно является слабым. $2+23=25$, но $25+5=30$ делится еще и на $3$. Значит, $s-r$ по меньшей мере равно $2$. Но $s-r$ не может быть равно даже $3$, т.к. наименьшее произведение оставшихся простых чисел $3\cdot 5\cdot 7=105>50=2\cdot 25$. Значит, $s-r=2$, причем одно из "добавляемых" простых чисел не может быть равно $5$ (т.к. иначе второе уже не будет простым). Наименьшее из двух "добавляемых" простых равно $3$, т.к. $7\cdot 11=77>50$. Тогда второе "добавляемое" простое является делителем $25+3=28$, т.е. $7$ (т.к. $2$ уже фигурирует в наборе). Но $28+7=35$ и делится на $5$, которого нет в наборе.
  2. Покажем, что все меньшие числа, являющиеся произведениями различных простых чисел - сильные.
    • $r=2$
      • $p_1=2$
        Отметаем меньшие числа в парах простых чисел-близнецов, т.к. для них $2+p_2+p_3=2\cdot p_3$ - условие выполнено. Остаются (в скобках указаны числа $\{p_1, p_2,\ldots,p_r\}$):
        • $(2+7)+3=12=2^2\cdot 3$
        • $(2+13)+3=18=2\cdot 3^2$
        • $(2+19)+3=24=2^3\cdot 3$
        • $2\cdot 23=46$
      • $p_1=3$
        • $(3+5)+2=10=2\cdot 5$
        • $(3+7)+2=12=2^2\cdot 3$
        • $(3+11)+2=16=2^4$
        • $(3+13)+2=18=2\cdot 3^2$
        • $3\cdot 17=51>46$
      • $p_1=5$
        • $(5+7)+2=14=2\cdot 7$
        • $5\cdot 11=55>46$
      • $p_1=7$
        • $7\cdot 11=77>46$
    • $r=3$
      • $p_1=2$
        • $p_2=3$
          • $2+3+5=10=2\cdot 5$
          • $2+3+7=12=2^2\cdot 3$
          • $2\cdot 3\cdot 11=66>46$
        • $p_2=5$
          • $2\cdot 5\cdot 7=70>46$
      • $p_1=3$
        • $3\cdot 5\cdot 7=105>46$
    • $r=4$
      • $2\cdot 3\cdot 5\cdot 7=210>46$


Обсуждение

Я не обнаружил никаких следов ММ227 в OEIS. Планирую исправить это упущение. При этом интересны не сила или слабость тех или иных наборов простых множителей, сравнение силы сильных.
Этот момент не нашел своего выражения в присланных решениях. Придется отдуваться ведущему.
Рассмотрим, например, наиболее простой класс сильных чисел - степени простых.
Для каждого $p$ уравнение $x = p^n\cdot sopf(x)$ разрешимо. При этом количество решений зависит только от $p$. Таким образом, возникает любопытное разбиение всех простых числел на классы.
К классу 1 относятся простые числа 2, 61, 97, 113, 151, 173...
К классу 2 - 3, 5, 17, 29, 41, 53, 73, 79...
К классу 3 - 7, 11, 13, 23, 37, 47, 89...
К классу 4 - 19, 31, 43, 67, 103, 131...
К классу 5 - 71, 179...
Естественно возникает вопрос о бесконечности классов для каждого натуральноо числа.
Более тонок вопрос об асимтотической плотности классов.

Задача ММ227 понравилась участникам. Даже если исключить мнение марафонцев, оценивающих задачи по однобалльной шкале, оценка останется высокой :-)
Такая ситуация весьма редка. Обычно, при достаточном количестве присланных решений палитра вкусовых предпочтений достаочно широка.

Разброс в призовых баллах тоже не слишком велик. Мне показалось недостаточно строгим обоснование слабости числа 46 Евгением Гужавиным. Это нашло отражение в оценке. Если Евгений докажет мне, что это я, а не он чего-то упустил готов пересмотреть его оценку.

Награды

За решение задачи ММ227 участники Марафона получают следующие призовые баллы:
Олег Полубасов - 9;
Анатолий Казмерчук - 8;
Владислав Франк, Владимир Дорофеев, Виктор Филимоненков, Валентина Колыбасова и Тимофей Игнатьев - по 7;
Евгений Гужавин - 6.

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


Вложения:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_227.pdf [314.74 Кб]
Скачиваний: 116
Комментарий к файлу: Решение Олега Полубасова
MM227_Polubasoff.pdf [332.72 Кб]
Скачиваний: 87
Комментарий к файлу: Решение Валентины Колыбасовой
MM227-2_Ariadna.pdf [150.08 Кб]
Скачиваний: 100
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение28.10.2017, 12:38 
Заслуженный участник


27/06/08
3552
Волгоград
===========ММ228===============

ММ228 (4 балла)

Какое наименьшее число элементарных четырехугольников может быть в конфигурации из семи прямых общего положения?

Решение

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

Обсуждение

Уже который год подряд в Марафоне наблюдается одна и та же тенденция: к концу конкурса значительная часть выдыхается и сходит с дистанции. В нынешнем конкурсе дистанция в 7 задач была пройдена достаточно дружно. Но в ММ228 обозначенная тенденция проявилась в полный рост - получено лишь 4 ответа.
И это при том, что эта задачка была запланирована в качестве легкого "разогрева" (или, если хотите пропедевтики) перед ММ229 и ММ230.

Большинство подобных задач решаются методом "пример+оценка". А для ММ228 достаточно лишь примера. Поэтому весьма сложная в целом задача о возможных количествах тех или иных многоугольников, возникающих при разбиении плоскости прямыми (многоугольника диагоналями и т.п.) в данном конкретном случае тривиализируется.

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

Однако никто из марафонцев не замахнулся (или замахнулся, но не ударил) на поиск наименьшего числа четырехугольников для более чем 7-и прямых.
Попробую хотя бы частично этот пробел.
Если я не ошибся при достаточно тупом переборном обосновании, для 8-и прямых наименьшее число четырехугольников - 1.
Похоже для 9-и прямых ответ тот же. Но в этом случае я даже не замахивался на перебор.

8 красных прямых на картинке образуют конфигурацию с вектором граней $(14,1,3,3,0,0)$.
Добавление 9-й (синей) прямой приводит к конфигурации $(18,1,6,3,0,0,0)$. (Два треугольника не полностью попали на картинку)

Изображение

Награды

За решение задачи ММ228 участники Марафона получают следующие призовые баллы:
Олег Полубасов и Анатолий Казмерчук - по 6;
Виктор Филимоненков и Валентина Колыбасова - по 4;

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


Вложения:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_228.pdf [1.81 Мб]
Скачиваний: 125
Комментарий к файлу: Решение Олега Полубасова
MM228_Polubasoff.pdf [264.34 Кб]
Скачиваний: 95
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение30.10.2017, 01:22 
Заслуженный участник


27/06/08
3552
Волгоград
Внимание!
Срок приема решений MM229 продлен до 24:00 8.11.17

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


16/06/10
199
Из условия ММ229:
«5) количество сторон выпуклой оболочки внешнего контура;

9) количество сторон внешнего контура?»

Непонятно, что такое «выпуклая оболочка внешнего контура». В терминологии к последним задачам об этом не сказано.

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


08/12/11
110
СПб
VAL сейчас читает лекции в "Сириусе", потому и срок приёма решений отодвинул.
Сказано, что внешний контур - это многоугольник. А что такое выпуклая оболочка многоугольника общеизвестно: это наименьший выпуклый многоугольник, содержащий заданный.

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


27/06/08
3552
Волгоград
Masik в сообщении #1261671 писал(а):
VAL сейчас читает лекции в "Сириусе"
Я их не читал, а, скорее, слушал. Впрочем, трибуной (и вниманием аудитории) на время овладеть удалось.
Цитата:
... потому и срок приёма решений отодвинул. Сказано, что внешний контур - это многоугольник. А что такое выпуклая оболочка многоугольника общеизвестно: это наименьший выпуклый многоугольник, содержащий заданный.
Спасибо! Я бы ответил так же.

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


08/12/11
110
СПб
Если это не будет противоречить правилам форума, расскажите, пожалуйста, вкратце о "Сириусе". По рассказам Константина Кнопа у меня создалось впечатление, что это очень хорошее начинание, поддерживающее не только олимпиадное движение, но и российскую науку в целом.

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


08/12/11
110
СПб
Уважаемый ведущий, продлите, пожалуйста, срок приема решений MM229 ещё на три дня, до 24:00 11.11.17.

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


27/06/08
3552
Волгоград
Masik в сообщении #1263293 писал(а):
Уважаемый ведущий, продлите, пожалуйста, срок приема решений MM229 ещё на три дня, до 24:00 11.11.17.

Ok

Срок приема решений MM229 продлен до 24:00 11.11.17

-- 08 ноя 2017, 15:11 --

Masik в сообщении #1263283 писал(а):
Если это не будет противоречить правилам форума, расскажите, пожалуйста, вкратце о "Сириусе". По рассказам Константина Кнопа у меня создалось впечатление, что это очень хорошее начинание, поддерживающее не только олимпиадное движение, но и российскую науку в целом.
Для подробного рассказа пока не готов - слишком много дел накопилось за время моего отсутствия.

А пока выскажу такое сомнение.
Практически одновременно произошли два события: открылся "Сириус" и прекратилось финансирование региональной программы "Архимед", направленной на работу с одаренными школьниками. Возможно, эти события никак не связаны, просто совпадение по времени. Тогда я двумя руками за "Сириус". А если связаны? Как бы ни был хорош "Сириус" одного центра работы с одаренными детьми для России маловато. Тем более, что только треть каждой смены (200 человек из 600) ориентирована на науку (остальные на искусство и спорт).

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


27/06/08
3552
Волгоград
===========ММ229===============

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

Петя нарисовал на доске несколько прямых общего положения так, что все попарные точки пересечения прямых попали на чертеж. Вася выписал себе в тетрадь внешний цикл возникшей конфигурации: (1, 4, 3, 1, 4, 1, 2, 2, 3, 2, 3, 1, 2, 3, 1, 2, 4, 2, 1, 3). После этого Петя стер рисунок. Сможет ли Вася восстановить:
1) количество прямых;
2) количество элементарных многоугольников:
3) количество выпуклых вершин;
4) количество элементарных отрезков, ограничивающих внешний контур;
5) количество сторон выпуклой оболочки внешнего контура;
6) суммарное число сторон элементарных многоугольников;
7) количество обратных вершин;
8) количество впадин;
9) количество сторон внешнего контура?

Примечание: Вася – умный.

Решение

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

Обсуждение

На перегоне ММ228-ММ229 никто из марафонцев с дистанции никто не сошел. Но, к сожалению, никто и не вернулся (примкнул).

Я не слишком высоко оценил титаническую работу Анатолия Казмерчука по подсчету количества конфигураций, приводящих к данному внешнему циклу, поскольку результат получился слишком уж частный.
Гораздо интереснее, на мой взгляд, получить какие-то общие закономерности.
Или хотя бы полное описание всех конфигураций (с позиций рассматриваемых конфигураций) для малого количества прямых.
До 4-х прямых включительно все однозначно.
При 5-и прямых все характеристики дружно перестают быть константами, но возможные значения легко перебираются.
Например, возможные векторы граней - [5,0,1], [4,1,1], [3,2,1], [3,3,0].
Разнообразие внешних циклов несколько больше:
(3,1,3,1,3,1,3,1,3,1);
(3,2,1,2,3,1,2,2,2,1);
(4,1,2,2,2,1,2,2,2,1);
(3,1,2,2,2,1,2,2,2,1);
(3,1,3,1,3,1,2,2,2,1);
(3,2,1,3,2,1,2,2,2,1).
В частности, для пяти прямых внешний цикл однозначно определяет вектор граней, что, как мы знаем, неверно в общем случае.
Начиная с 6-и прямых, разнообразие характеристик и их сочетаний уже настолько велико, что ручной перебор проблематичен.
Ну а в общем случае...
В общем случае удается получить лишь некоторые оценки. Такие как наличие $n-2$ треугольников и достижимость $\frac{(n-2)(n-3))}2$ четырехугольников для конфигураций из $n$ прямых.

Награды

За решение задачи ММ229 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 9;
Олег Полубасов - 8;
Виктор Филимоненков - 7;
Валентина Колыбасова - 6.

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


Вложения:
Комментарий к файлу: Решение Олега Полубасова
MM229_Polubasoff_.pdf [403.77 Кб]
Скачиваний: 100
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_229-1.pdf [986.61 Кб]
Скачиваний: 156
Комментарий к файлу: Решение Виктора Филимоненкова
fiviol_mm229.docx [47.58 Кб]
Скачиваний: 92
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение12.11.2017, 13:59 
Аватара пользователя


08/12/11
110
СПб
Трёхвершинная выпуклая оболочка всё-таки оказалась возможной! Я искренне заблуждался.
Жаль, что никто не рассмотрел вопрос, каким соотношениям должны удовлетворять внешние циклы конфигураций.

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


27/06/08
3552
Волгоград
В связи с малочисленностью откликов и поступившей просьбой срок приема решений ММ230 продлен на неделю, до 8.12.17

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


27/06/08
3552
Волгоград
===========ММ230===============

ММ230 (15 баллов)

Может ли вектор граней конфигурации нескольких прямых общего положения начинаться с чисел 157, 5250, 52?

Решение

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

Обсуждение

При составлении ММ230 я не избежал соблазна облегчить жизнь ведущему (при одновременном усложнении жизни конкурсантов).
Как правило, изобретая задачу для Марафона, я колдую над ней, как минимум, не меньше, чем те, кто будет ее решать.
С ММ230 картина иная. Я затратил на ее составление минут пятнадцать, при этом отдавая себе отчет (см. разбалловку) сколь тяжко будет конкурсантам.
Я рассмотрел конфигурацию из $n-1 =2k-1 (k>2)$ прямых, являющихся сторонами правильного многоугольника.
Ясно что, вектор грани конфигурации - $(n-1,\frac{(n-1)(n-6)}2,0,\dots,0,1)$.
Осталось добавить к конфигурации n-ную прямую так, чтобы все точки пересечения остальных прямых лежали по одну сторону от этой прямой.
Теперь возьмем какое-нибудь большое $k$ (например 53), и пыточная камера для конкурсантов готова.

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

Я сначала отрезал, было, от решения Анатолия Казмерчука кусок ММ229, но потом понял, что он ссылается на введенные там обозначения и полученные соотношения.

В решении Олега Полубасова меня восхитило то, с каким изяществом он описал все возможные векторы граней, начинающиеся с указанной тройки.

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

Награды

За решение (продвижение в сторону решения, решение и исследование) задачи ММ230 участники Марафона получают следующие призовые баллы:
Олег Полубасов - 20;
Анатолий Казмерчук - 17;
Виктор Филимоненков - 5;
Валентина Колыбасова - 4.

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

Итоги конкурса постараюсь подвести в ближайшее время.


Вложения:
Комментарий к файлу: Решение Олега Полубасова
MM230_Polubasoff.pdf [505.14 Кб]
Скачиваний: 222
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_230.pdf [428.96 Кб]
Скачиваний: 185
 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 836 ]  На страницу Пред.  1 ... 36, 37, 38, 39, 40, 41, 42 ... 56  След.

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



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

Сейчас этот форум просматривают: GoGo [bot]


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

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