Различия

Здесь показаны различия между двумя версиями данной страницы.

--- marathon:about [2016/11/27 07:35]
letsko [ММ219]
+++ marathon:about [2021/06/17 17:02] (текущий)
letsko [Текущие задачи]
@@ Строка 8: / Строка 8: @@
 ----
+**Завершен XXVII конкурс вамках Математического марафона**
-Продолжается **22-й конкурс в рамках Математического марафона**
+**Мои поздравления победителю конкурса, Мерабу Левиашвили, призерам, Анатолию Казмерчуку и Олегу Полубасову, а также всем тем, кто составил им достойную конкуренцию**
-Старожилы Марафона, наверняка, обратили внимание, что привычное слово "тур" заменено на "конкурс". Это сделано, чтобы подчеркнуть самостоятельность этого соревнования.
-В связи с этим и рядом других накопившихся изменений в правила Марафона внесены некоторые уточнения.
--й конкурс - тематический. Во всех задачах тура, кроме ММ216, речь пойдет о выпуклых многогранниках.
-Во всех задачах, где речь идет о многогранниках, под словом "многогранник" подразумевается выпуклый многогранник.
 Стать участником марафона может любой желающий. Некоторые задачи вполне доступны школьникам. Для решения других требуются знания, выходящие за рамки школьного курса. Одни задачи могут показаться вам интересными, а другие - не очень. На вкус и на цвет...
-Но если любите поломать голову над нестандартными задачами, участвуйте, не стесняйтесь.
+Но если вы любите поломать голову над нестандартными задачами, участвуйте, не стесняйтесь.
 Жду от вас комментариев марафонских задач, а также пожеланий Марафону. Эта обратная связь позволит сделать Марафон интереснее для вас.
 Не забывайте, пожалуйста, присылать вместе с Вашими решениями свои эстетические оценки задач по пятибалльной шкале.
-----
  Ведущий Марафона
 --- //[[val-etc@yandex.ru|Vladimir letsko]]//
+[[Afterword XXVII |Послесловие к XXVII конкурсу]]
 ----
@@ Строка 35: / Строка 31: @@
 ====== Текущие задачи ======
 ----
+**На данный момент отсутствуют.**
-===== ММ219 =====
-**Конкурсная задача ММ219** (8 баллов)
-Решения принимаются до 22:00 (мск) __29.11.2016__
-Какое наибольшее количество диагоналей может иметь одиннадцатигранник?
 ----
-===== ММ220 =====
+====== Разбор задач ======
-**Конкурсная задача ММ217** (15 баллов)
-Решения принимаются до __17.12.2016__
-Найти наименьшее v такое, что существует многогранник, имеющий v вершин и 2016 диагоналей, а многогранника, имеющего v+1 вершину и 2016 диагоналей, не существует.
 ----
+=====
+Вектором граней выпуклого многогранника P назовем набор [f<sub>3</sub>, f<sub>4</sub>, …, f<sub>s</sub>], где f<sub>i</sub> – количество i-угольных граней P, а s - наибольшее число сторон грани. Будем говорить, что P относится к классу m, если max(f<sub>i</sub>) = m.
-====== Разбор задач ======
 ----
-=====ММ218=====
-**Конкурсная задача ММ218** (5 баллов)
+**Конкурсная задача ММ270** (16 баллов)
-Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.
+Найти наибольшее возможное количество граней многогранника класса m.
 **Решение**
-Привожу решения Владимира Чубанова, {{:marathon:mm218_polubasoff.pdf|Олега Полубасова}}, {{:marathon:kazmerchuk_pr_218_1.docx|Анатолия Казмерчука}} и {{:marathon:frank_mm218.pdf|Владислава Франка}}.
+Привожу решения призеров конкурса, {{:marathon:mm_270_polubasoff.pdf|Олега Полубасова}} и {{:marathon:kazmerchuk_mm_270.pdf|Анатолия Казмерчука}}, а также обобщение задачи победителя конкурса {{:marathon:обобщение-мм270.docx|Мераба Левиашвили}} .
-**Решение Владимира Чубанова**
+**Обсуждение**
-ММ218
+В отличие от ММ269, где вопрос задачи был сформулирован для частных значений m, а обобщали его сами конкурсанты, в ММ270 сразу же был сформулирован общий вопрос. Объясняется это просто. В ММ269 ответа на общий вопрос ведущий на момент опубликования задачи не знал (и даже склонялся, но, к счастью не "доказал" неверный ответ). А для ММ270 у меня был верный обоснованный ответ.
-Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.
+Эта ситуация выбила почву из под ног большинства любителей обобщений. Да, практически все, решившие ММ270, нашли заодно и наибольшие количества вершин и ребер m-многогранников. Но ответы на эти вопросы становятся очевидны при успешном решении основной задачи. Единственным, кто изыскал возможности пообобщать стал Мераб Левиашвили. Он перешел от рассмотрения многогранников к рассмотрению простых (каждая вершина имеет степень n) политопов размерностей, больших 3. У таких политопов существуют грани разных размерностей. Соответственно можно рассматривать разные аналоги m-многогранников. Мераб остановился на случае двумерных граней. На основании известных соотношений Дена-Соммервиля он получил наименьшие значения m, для которых существуют n-мерные политопы класса m и верхние оценки для числа граней таких политопов для n \in {4, 5}, а также некоторые оценки для n \in {6, 7, 8}. Я привожу только обобщение задачи (присланное Мерабом отдельным документом), в том числе, и по причине слишком большого веса основного решения.
-Ответ: 1004 диагоналей.
+Во всех присланных решениях имеется содержится ответ 7m-4 для больших значений m. Разнятся эти решения степенью гипотетичности и обоснованности данного ответа, а также количеством частных значений m, подтверждающих данную гипотезу (это касается решений, где 7m-4 именно гипотеза).
-{{ :marathon:pic_mm218.png?200 |[img]http://s019.radikal.ru/i600/1611/e3/e8f7633cbe66.png[/img]|рис. 1}}
-Пример на 1004 построить легко (см. рисунок). Поставили треугольную призму "домиком" и с одной стороны -- со стороны AB -- добавили 1004 точки в плоскости ABDF (на рисунке отмечена только часть этих точек). Получили 1008 точек основания и 2 точки "сверху".\\
-Количество рёбер: 1008+1004+4+1 = 2017;\\
-Количество (пространственных) диагоналей: 1004 -- все новые точки соединены с т.E. Других диагоналей нет.\\
-Аргументы в пользу того, что меньше быть не может.\\
+**Награды**
-При рассмотрении суммарно всех диагоналей (пространственные + диагонали граней) нетрудно заметить, что наиболее выгодная стратегия лежит не в уменьшении числа вершин и не в разделении вершин по разным граням, а в максимальной консолидации вершин в одной грани-плоскости (поскольку \binom{n}{2} растёт квадратично, при таком количестве точек это перевешивает остальные стратегии).\\
-Поднять только одну вершину над плоскостью недостаточно -- количество рёбер будет чётным.\\
-Поднять 2 вершины над плоскостью можно несколькими принципиально разными способами, которые несложно перебрать руками и убедиться, что представленный вариант принадлежит множеству самых выгодных.
-Кроме того, приведу и свое решение задачи.
+За решение задачи ММ270 участники Марафона получают следующие призовые баллы:\\
+Мераб Левиашвили - 18;\\
+Олег Полубасов - 16;\\
+Анатолий Казмерчук - 16;\\
+Александр Романов - 16;\\
+Константин Шамсутдинов - 10;\\
+Виктор Филимоненков - 10;\\
+Денис Овчинников - 8.\\
-**Авторское решение**
+Эстетическая оценка задачи - 4.8 балла
-Я специально не стал заострять внимание на технических деталях, чтобы не скрыть в них основные (довольно простые) идеи.
+----
-Пусть многогранник имеет v вершин, e ребер и f граней, а h<sub>1</sub>,h<sub>2</sub>, ..., <sub>f</sub> - количества сторон граней. Очевидно, что количество ребер такого многогранника многогранника вычисляется по формуле:\\
-<m>d=({matrix{2}{1}{{v}{2}}}) - e-1/2 sum{i=1}{f}{h_i(h_i-3)}</m> (1)
+===== ММ269 =====
-Легко видеть, что при фиксированных e и f  сумма
+ **Конкурсная задача ММ269** (11 баллов)
-<m>1/2 sum{i=1}{f}{h_i(h_i-3)}</m>
+Какова максимальная возможная степень вершины выпуклого многогранника\\
+a) класса 3;\\
+b) класса 4?
-будет тем меньше, чем равномернее распределены значения h<sub>i</sub>. И, соответственно, тем больше, чем больше самое большое из h<sub>i</sub> (в дальнейшем будем считать, что это h<sub>1</sub>.\\
+**Решение**
-При четных e h<sub>1</sub> может достигать e/2. Этот случай соответствует пирамидам, у которых d=0.
-В нашем случае наибольшее значение h<sub>1</sub> = 1008 достигается при v = 1010, f = 1009. Соответствующие многогранники (еще две его грани четырехугольны, а остальные треугольны) легко строится. Их изображения можно найти в некоторых из приводимых решений. По формуле (1) (или в лоб) находим, что для такого многогранника d = 1004.
+Привожу решения {{:marathon:mm269_polubasoff.pdf|Олега Полубасова}}, {{:marathon:kazmerchuk_mm_269.pdf|Анатолия Казмерчука}} и {{:marathon:shamsutdinov_mm269.docx|Константина Шамсутдинова}}.
-Ясно, что с ростом v уменьшаемое в (1) будет расти, а вычитаемое уменьшаться. Следовательно будет расти и d.
+**Обсуждение**
-Картина, возникающая при уменьшении v, не столь очевидна. Ведь в этом случае в (1) будут уменьшаться и уменьшаемое и вычитаемое.\\
+Согласно традициям Марафона последние задачи каждого конкурса имеют повышенную сложность. Эта традиция сохранилась и в данном конкурсе.
-Так, при v = 1009, f = 1010  существует многогранник, имеющий одну 1007-угольную и 1009 треугольных граней. Впрочем, для того, чтобы понять, что у него больше диагоналей, чем вышеописанный, даже не нужно прибегать к формуле (1). Ведь, чтобы получить новый многогранник из предыдущего, достаточно малым шевелением:\\
+Результатом этого усложнения чаще всего был отток значительной части конкурсантов. А эта традиция неожиданно была нарушена! Из тех, кто регулярно участвовал в нынешнем конкурсе, не прислали решения ММ269 всего два человека. А остальные порадовали, но не пощадили ведущего :-) Впрочем, после моей мольбы, все же сжалились, сократив самое длинное из решений на 40(!) страниц.
-а) перегнуть четырехугольные грани по диагонали (при этом добавятся две грани, два ребра и две диагонали);\\
-б) спрямить одну из сторон 1008-угольного основания (при этом уйдут одна вершина, одна грань, два ребра и одна диагональ).\\
-Итого, у нового многогранника получится 1004+2-1 = 1005 диагоналей.
-Но уже следующее уменьшение v на 1 приведет к лавинообразному росту d. В самом деле, пусть v = 1008, f = 1011. Тогда наибольшее возможное значение h<sub>1</sub> равно 1004 (иначе просто некуда будет "впихнуть" необходимое количество граней и ребер). Остальные 1010 грани - треугольники ((см. соответствующий граф на рисунке). Для такого многогранника формула (1) дает d=3009.
+Разумеется, основные страсти кипели вокруг обобщения задачи, очевидного по постановке вопроса. Но только по постановке. Да-да, ответ 3m-3 не годится!
+В какой-то момент у меня имелось три решения, в которых приводилась и обосновывалась точная формула для максимальной возможной степени вершины m-многогранника. Точнее, три разных формулы, дающих разные ответы :-)\\
+Понимая, что ситуация, когда "Вася и Петя оба правы", маловероятна, ведущий был вынужден углубиться в многостраничные трактаты, воспользовавшись удачно подвернувшейся просьбой продлить срок приема решений. Дополнительное время не пропало даром. И ведущий и конкурсанты обнаружили некоторые ошибки и неточности в решениях. Во всех, кроме одного, в котором ошибок найти не удалось (или, все же, пока не удалось?). Желающие могут попробовать определить это решение из приводимого ниже списка начисленных призовых баллов (а также попытаться найти ошибки и в этом решении).
-{{ :marathon:pic_mm218_val.png?200 |рис.1}}
+**Награды**
-При дальнейшем уменьшении v наибольшее возможное h<sub>1</sub> убывает более быстрыми темпами и, следовательно, d растет. Так, при наименьшем возможном v, равном 675, наибольшее h<sub>1</sub> будет 5, а d=675·674/2-2017-5 = 225453.
+За решение задачи ММ269 участники Марафона получают следующие призовые баллы: \\
+Олег Полубасов - 18;\\
+Мераб Левиашвили - 16;\\
+Анатолий Казмерчук - 13;\\
+Константин Шамсутдинов - 13;\\
+Василий Дзюбенко - 11;\\
+Александр Романов - 11;\\
+Виктор Филимоненков - 11;\\
+Денис Овчинников - 7.
-**Обсуждение**
+**Эстетическая оценка задачи - 4.7 балла**
+----
-Подзаголовок "От двух до пяти", смутивший одних и вдохновивших других марафонцев, случайно достался этой задаче в наследство от ММ208.
-Судя по присланным решениям, ММ218 оказалась достаточно сложной. Я же рассматривал ее, как весьма простую. По-видимому, это следствие того, что данную задачу я поставил уже после того, как исследовал вопросы о количестве диагоналей многогранников с фиксированным количеством вершин (граней). В частности, к этому времени я уже знал (и умел доказывать), что для минимизации количества диагоналей надо максимизировать число сторон самой большой грани.
+===== ММ268 =====
-Чтобы понять, насколько по-разному воспринимали сложность задачи участники и ведущий достаточно сравнить авторское решение с решением Владислава Франка, в котором Влад долго и скрупулезно обосновывает... неверный ответ :-) Сразу отмечу (а то, ведь, не каждый осилит несколько страниц), что в решении Влада есть и верный ответ, но Влад предпочел сохранить в итоговом варианте весь тернистый путь к нему.
-Изначально я планировал давать 5 баллов за решения, в которых будут указаны многогранники с 1004 и 1055 диагоналями и приведены (возможно, не идеально строгие, но убедительные) соображения, подтверждающие невозможность меньшего числа диагоналей. Т. е. близкие к тому, что приведено мной. Но в процессе изучения решений участников, я слегка персмотрел эти критерии в сторону увеличения призовых баллов. Я старался не замечать откровения типа 553+553 = 1006 :) По крайней мере, при оценивании.
+**Конкурсная задача ММ268** (9 баллов)
-Разумеется, число 2017 не особенное по отношению к ММ218. Важна лишь его нечетность. Мне понравилось, что формула d=(e-9)/2 возвращает наименьшее возможное количество диагоналей многогранника с нечетным числом ребер для всех без исключения допустимых значений e и дает заведомо бессмысленные значения для тех e, для которых не существует многогранников. Многие другие формулы, связанные с количеством диагоналей многогранников, допускают исключения для малых значений параметров.
+Назовем натуральное число m допустимым, если существует такое n, что из чисел 1,2,…,n можно составить сумму произведений, в которой каждое число встречается ровно один раз, равную m. Сколько существует недопустимых чисел?
-**Награды**
+Примечание: в суммах произведений допускаются одиночные слагаемые. Например, число 148 допустимо, поскольку 148=1·3 + 2·5·8 + 4 + 6·9 + 7.
-За решение ММ218 участникам начислены следующие призовые баллы:\\
+[[problem 268|Решение задачи ММ268]]
-Владислав Франк, Олег Полубасов и Анатолий Казмерчук - по 8;\\
-Владимир Чубанов - 6;\\
-Виктор Филимоненков и Владимир Дорофеев - по 4.\\
-**Эстетическая оценка задачи - 4.2 балла**
 ----
-=====ММ217=====
-**Конкурсная задача ММ217** (6 баллов)
-Диагонали AC<sub>1</sub> и BD<sub>1</sub> шестигранника ABCDA<sub>1</sub>B<sub>1</sub>C<sub>1</sub>D<sub>1</sub>, все грани которого четырехугольны, пересекаются в точке O.  Могут ли остальные пары диагоналей скрещиваться?
+===== ММ267 =====
+**Конкурсная задача ММ267** (7 баллов)
+Вася и Петя поспорили. Вася уверен, что среди представлений натурального числа n в виде суммы натуральных слагаемых чаще встречаются те, у которых каждое слагаемое присутствует не более двух раз, чем те, у которых все слагаемые не кратны 3. Петя уверен в обратном. Кто из них прав?
+[[problem 267|Решение задачи ММ267]]
-[[problem 217|Решение задачи ММ217]]
 ----
-=====ММ216=====
+===== ММ266 =====
-**Конкурсная задача ММ216** (10 баллов)
+**Конкурсная задача ММ266** (7 баллов)
-Назовем натуральное число n красивым, если наименьшее натуральное число, имеющее ровно n натуральных делителей, кратно n.\\
+Вася Пупкин выписал дни рождения семерых своих однокурсников, родившихся в январе одного и того же года, что и Вася, и, поэкспериментировав с выписанными числами, заметил два факта:\\
-. Доказать, что все праймориалы красивы.\\
+) τ(n<sup>3</sup> )=τ(n)<sup>2</sup>, где n – произведение всех выписанных чисел;\\
-. Верно ли, что все факториалы красивы?\\
+) сумма кубов составных чисел больше суммы кубов остальных\\.
-. Сколько существует красивых чисел вида k<sup>7</sup>, где k - некоторое натуральное число?\\
+Найдите дни рождения Васиных товарищей, если известно, что все они младше Васи.
-. Сколько существует красивых чисел вида 7k<sup>k</sup>, где k - некоторое натуральное число?
+Примечание: при сравнении возрастов учитываются дни, но не часы рождения.
+[[problem 266|Решение задачи ММ266]]
-[[problem 216|Решение задачи ММ216]]
 ----
-=====ММ215=====
+===== ММ265 =====
-**Конкурсная задача ММ215** (4 балла)
+**Конкурсная задача ММ265** (5 баллов)
-На какое наименьшее количество тетраэдров можно разрезать шестиугольную призму?
+Разрезать правильный треугольник на наименьшее возможное количество прямоугольных треугольников так, чтобы никакие два из возникших треугольников не были подобны.
+[[problem 265|Решение задачи ММ265]]
-[[problem 215|Решение задачи ММ215]]
 ----
-=====ММ214=====
+===== ММ264 =====
+**Конкурсная задача ММ264** (4 балла)
+Назовем пару натуральных чисел a и b аддитивной, если τ(a+b)=τ(a)+τ(b),σ(a+b)=σ(a)+σ(b)  и φ(a+b)=φ(a)+φ(b).
+Доказать, что существует бесконечно много аддитивных пар.\\
-**Конкурсная задача ММ214** (4 балла)
+(τ(n), σ(n), φ(n) - количество натуральных делителей, сумма натуральных делителей и функция Эйлера соответственно.)
-. Все грани многогранника - n-угольники. При каких n это возможно?\\
+[[problem 264|Решение задачи ММ264]]
-. При каком наименьшем числе граней существует многогранник, все грани которого пятиугольны?
-[[problem 214|Решение задачи ММ214]]
 ----
+===== ММ263 =====
+ **Конкурсная задача ММ263** (4 балла)
-=====ММ213=====
+Сколько решений может иметь уравнение [3x]{x} – [x]{3x} = c, в зависимости от значения параметра c?\\
-**Конкурсная задача ММ213** (4 балла)
+([x] и {x} означают соответственно целую часть (пол) и дробную часть числа x.)
-. Пусть  H = {h<sub>1</sub>, h_2,...,  h<sub>f</sub>} , где  f  - количество граней, а  h<sub>i</sub>  - число сторон  i -й грани. Какое наименьшее значение может принимать f-|H| ?\\
+[[problem 263|Решение задачи ММ263]]
-. Пусть g<sub>i</sub> означает число i-угольных граней многогранника для каждого значения i . Могут ли все g<sub>i</sub> не превышать 2?
-[[problem 213|Решение задачи ММ213]]
 ----
-=====ММ212=====
-**Конкурсная задача ММ212** (4 балла)
+===== ММ262 =====
+**Конкурсная задача ММ262** (3 балла)
-Доказать, что любой многогранник, имеющий 2016 вершин, может быть разрезан на  4030 тетраэдров.
+Разносторонний треугольник назовем прогрессивным, если длины его сторон образуют арифметическую прогрессию.
+Доказать, что треугольник прогрессивен тогда и только тогда, когда прямая, проходящая через точку Нагеля и центр Шпикера, параллельна средней стороне.
-**Решение**
+Примечание: тривиальное решение (недаром цена задачи всего 3 балла) на ЕГЭ бы не приняли, но у нас, слава Богу, не ЕГЭ :-)
-[[problem 212|Решение задачи ММ212]]
+[[problem 262|Решение задачи ММ262]]
-----
-=====ММ211=====
+----
+===== ММ261 =====
+**Конкурсная задача ММ261** (4 балла)
-**Конкурсная задача ММ211** (3 балла)
+Натуральные числа 1, 2, 3, ..., 100 разбили на 10 групп по 10 чисел. Найти наибольшую возможную сумму НОД этих десяток.
-Доказать, что при любом четном f > 4 существует многогранник, имеющий f граней, все грани которого четырехугольники.
+[[problem 261|Решение задачи ММ261]]
-[[problem 211|Решение задачи ММ211]]
 ----
 ~~NOTOC~~