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

[Masik]

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

[rockclimber]

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

[VAL]

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

[VAL]

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

[VAL]

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

[lim0n]

Из условия ММ229:
«5) количество сторон выпуклой оболочки внешнего контура;
…
9) количество сторон внешнего контура?»

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

[Masik]

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

[VAL]

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

VAL сейчас читает лекции в "Сириусе"

Я их не читал, а, скорее, слушал. Впрочем, трибуной (и вниманием аудитории) на время овладеть удалось.

Цитата:

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

Спасибо! Я бы ответил так же.

[Masik]

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

[Masik]

Уважаемый ведущий, продлите, пожалуйста, срок приема решений MM229 ещё на три дня, до 24:00 11.11.17.

[VAL]

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

Уважаемый ведущий, продлите, пожалуйста, срок приема решений MM229 ещё на три дня, до 24:00 11.11.17.

Ok

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

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

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

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

Для подробного рассказа пока не готов - слишком много дел накопилось за время моего отсутствия.

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

[VAL]

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

[Masik]

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

[VAL]

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

[VAL]

===========ММ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 баллов

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