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

[VAL]

================

Оценка за решение задачи ММ128 учитывается дважды в основном Марафоне и в тематическом конкурсе.

ММ128 (КГ-10) (20 баллов)

На сколько классов изополярных восьмиугольников разбиваются выпуклые восьмиугольники?

================

Решение

Очевидно, что у выпуклого восьмиугольника может быть не более одного полюса второго порядка. А из рассуждений, приведенных при разборе задачи ММ102, следует, что общее число полюсов не может превышать девяти. Поэтому число классов изополярных восьмиугольников не превышает 19.
Ниже приведены представители 17 классов изополярных восьмиугольников. Для каждого случая приводится не только рисунок, но и координаты вершин, дабы желающие (если таковые найдутся :) ) могли убедиться, что все без обмана.

1. $(120,20), (80,80), (-20,120), (-80,65), (-100,0), (-80,-80), (-5,-100), (80,-80)$


2. $(120,20),(80,80),(-33,120),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


3. $(120,30),(80,80),(0,120),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


4. $(120,0),(\frac{13520}{97}, \frac{10320}{97}),(0,100),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


5. $(100,0),(\frac{5200}{57}, \frac{2000}{57}),(0,100),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


6. $(\frac{2425}{13}, -\frac{500}{13}),(80,80),(0,100),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


7. $(120,0),(\frac{3920}{29},\frac{2960}{29}),(0,120),(-80,80),(-120,0),(-80,-80),(0,-120),(80,-80)$


8. $(100,\frac{225}{14}),(90,45),(0,50),(-90,45),(-100,\frac{225}{14}),(-90,-45),(0,-\frac{475}{9}),(90,-45)$


9. $(\frac{35}{9}, -100), (70, -70), (115, \frac{35}{18}), (70, 70), (\frac{35}{9}, \frac{768}{7}), (-70, 70), (-\frac{1815}{19}, \frac{35}{18}), (-70, -70)$


10. $(0, -100), (70, -70), (\frac{985}{9}, \frac{35}{9}), (70, 70), (0, 120), (-70, 70), (-\frac{985}{9}, \frac{35}{9}), (-70, -70)$


11. $(120,0),(80,80),(0,120),(-80,80),(-100,0),(-80,-80),(0,-100),(100,-100)$


12. $(120,0),(80,80),(0,120),(-80,80),(-100,0),(-\frac{1800}{23},-\frac{1800}{23}),(0,-100),(90,-90)$


13. $(120,0),(80,80),(0,120),(-80,80),(-100,0),(-80,-80),(0,-100),(80,-80)$


14. $(120,0),(80,80),(0,100),(-80,80),(-100,0),(-\frac{1200}{17},-\frac{1200}{17}),(0,-100),(80,-80)$


15. $(10,-20),(20,-10),(20,10),(10,20),(-10,20),(-20,10),(-20,-10),(-10,-20)$


16. $(\frac{1900}{9},0),(90,90),(0,100),(-90,90),(-100,0),(-90,-90),(0,-100),(90,-90)$


17. $(100,0),(\frac{1180}{11},\frac{840}{11}),(20,60),(-\frac{310}{13},\frac{420}{13}),(-\frac{75}{2},0),(-\frac{1180}{31},-\frac{840}{31}),(-\frac{280}{19},-\frac{840}{19}),(\frac{155}{4},-\frac{105}{2})$


У меня нет строгого доказательства отсутствия классов с характеристическими векторами (5, 1) и (7, 1). Но есть соображения (не оставляющие лично у меня сомнения в том, что таких восьмиугольников не существует). Они приведены в обсуждении.

Обсуждение

Вслед за Сергеем Половинкиным диагональ многоугольника буду называть i-диагональю, если между вершинами, которые она соединяет, (на ломаной из сторон, содержащей наименьшее число звеньев) расположено i вершин исходного многоугольника. Такая терминология представляется мне более удобной, чем та (с "короткими", "средними" и "длинными" диагоналями), которую я использовал раньше.

Ясно, что, если в восьмиугольнике есть полюс второго порядка, полюса первого порядка могут быть расположены либо на пересечени двух 2-диагоналей и одной 3-диагонали, либо на пересечении трех 2-диагоналей.
Координаты вершин многоугольника с рисунка 17 были получены следующим образом:
Несколько вершин (полагаю не сложно догадаться какие) и полюсов были подобраны заранее. Положение остальных зависело от неких параметров. Затем составлялась система, позволяющая найти такие значения параметров, при которых получался бы восьмиугольник, имеющий один полюс второго порядка и пять полюсов типа 2-2-3.
Однако, полученный таким образом восьмиугольник имеет не пять, а целых восемь полюсов первого порядка (все типа 2-2-3). Учитывая, что я специально строил восьмиугольник, не обладающий какими-либо очевидными симметриями, гипотеза о том, что еще целых три полюса образовались случайно, выглядит не слишком правдоподобной :) Тем более, что картина повторяется при построении восьмиугольника с другими начальным данными.
Полагаю, эти примеры убедительно свидетельствуют: наличие одного полюса второго порядка и пяти полюсов типа 2-2-3, автоматически влечет появление еще трех таких же полюсов.
Значит, надо искать среди многоугольников имеющих полюса типа 2-2-2.

В какой-то момент времени я был близок к мысли, что мне вот-вот удастся построить восьмиугольник с характеристическим вектором (5, 1). Казалось бы, достаточно немного "пошевелить" восьмиугольник, изображенный на рисунке 18-1, и цель будет накрыта!


И я "пошевелил". Результат Вы можете видеть на рисунке 18-2. Как только вершины были подвинуты так, чтобы близкие точки пересечения диагоналей стянулись в один полюс второго порядка, четыре полюса типа 2-2-3 и один полюс типа 2-2-2, как черт и табакерки выскочил еще один полюс типа 2-2-2, на который до "шевеления" не было даже намека.


Координаты вершин возникшего восьмиугольника с характеристическим вектором (6-1), на мой взгляд, исключают гипотезу случайного появления дополнительного полюса:
$(-40, -35),(\frac{2164204000}{4449630273}, -\frac{68234660000}{1483210091}),(42, -45),(100, 0),(\frac{62160000}{693907}, \frac{54390000}{693907}),(-\frac{6492612000}{3300366221}, \frac{614111940000}{3300366221}),(-\frac{3108000}{18049}, \frac{3330000}{18049}),(-105, 0)$

Восьмиугольник с рисунка 18-2 сыграл со мной злую шутку. Изучая его, я обнаружил, что все шесть полюсов первого порядка лежат на одном эллипсе (это достоверный факт, я подставлял координаты в уравнение). После этого я решил, что для строгого обоснования невозможности случаев (5, 1) и (7, 1) надо "копать" в сторону терем Паскаля, Брианшона, Штейнера еtc. И копал...
Но вот Анатолий Казмерчук прислал "обоснование" существования восьмиугольника типа (5, 1). Он поступил аналогично тому, как поступал я, с той разницей, что не стал отыскивать требуемое значение параметра, а лишь наметил план и указал, что по соображениям непрерывности такое значение обязательно найдется.
Наученный предыдущим опытом, я не сомневался, что одновременно с пятым полюсом первого порядка образуется и шестой, и что эти шесть полюсов лягут на один эллипс.
Первая гипотеза подтвердилась. А вот вторая... Здесь и подставлять ничего не надо, достаточно взглянуть на рисунок 19.


По традиции приведу координаты вершин: $(0, 55), (\frac{400}7, \frac{300}7), (\frac{880}{13}, 0), (40, -30), (0, -\frac{66550}{983}), (-\frac{4400}{133}, -\frac{3300}{133}), (-50, 0), (-44, 33)$

Мне по-прежнему не верится в случайность попадания шести полюсов многоугольника с рисунка 18-2 на один эллипс. Возможно так будет всегда, когда полюса типа 2-2-2 оказываются напротив друг друга. (Рисунок 16 показывает, что обращение этой гипотезы места не имеет.) Я наверняка постараюсь внести ясность в этот вопрос. Хотя построение примеров - вещь довольно утомительная. Даже с применением мат. пакетов.

Попытки построения восьмиугольника с характеристическим вектором (5, 1) и тремя полюсами типа 2-2-2 привели меня лишь к вырожденным "восьмиугольникам", у которых "склеиваются" несколько вершин.

Отмечу, что класс преобразований, не нарушающих изополярности восьмиугольника (даже имеющего много полюсов), довольно широк.
Например, ясно что проективное преобразование, сохраняя прямолинейность и инцидентность, переведет восьмиугольник в изополярный. (Если мы работаем на расширенной плоскости, то важно, чтобы прямая, образ которой будет несобственной прямой, не "цепляла" восьмиугольник.)
Однако даже в наиболее "узком" классе изополярных многоугольников с характеристическим вектором (8, 1) есть такие, которые не могут быть переведены друг в друга проективным преобразованием. Это следует хотя бы из того, что проективные преобразования сохраняют кривые второго порядка. В то же время, восьмиугольник с рисунка 17 не вписывается в кривую второго порядка, в отличие от правильного восьмиугольника, имеющего тот же характеристический вектор.

Алексей Волошин, единственный из участников представивший законченное описание представителей классов (с указанием координат всех вершин), отталкивался от различных правильных многоугольников. В результате, в его примерах координаты многих вершин иррациональны, в отличие от восьмиугольников, приведенных на рисунках 1-17.
Полагаю, что для произвольных выпуклых n-угольников ситуация такая же: в каждом классе изополярных многоугольников найдется представитель, у которого координаты всех вершин рациональны (если надо, то и целы).

В общем случае из изополярности восьмиугольников, разумеется, не следует их однотипность и, тем более. изотопность. Однако для восьмиугольников, насыщенных полюсами, картина иная. Так, все восьмиугольники с характеристическим вектором (8, 1), очевидно, изотопны. Восьмиугольники с характеристическим вектором (6, 1) уже могут быть не изотопны (см. рис. 18-2 и рис 19), но, по-видимому, всегда однотипны. Похоже , что однотипны, а возможно, и изотопны, будут и восьмиугольники с векторами (9, 0) и (8, 0).

Интересно, что в разбиении восьмиугольников с характеристическими векторами (8, 1), (6, 1) и (9, 0) встречаются только треугольники и четырехугольники.

Задачи нахождения чисел классов однотипных и изотопных восьмиугольников представляются весьма сложными. В любом случае счет идет на тысячи.

Награды

За решение задачи ММ128 Алексей Волошин получает 18 призовых баллов, Анатолий Казмерчук - 12 призовых баллов, а Сергей Половинкин - 10 призовых баллов.

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

================

Разбор задачи ММ128 подготовлен Владимиром Лецко.

-- 16 окт 2010, 11:49 --

====================================

Итоговое положение участников
в XIII туре Математического марафона
\displaystyle \begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline & & 121 & 122 & 123 & 124 & 125 & 126 & 127 & 128 & 129 & 130 & \Sigma \\ \hline 1.& Анатолий Казмерчук & 8 & 4 & 5 & 4 & 2 & 3 & 12 & 12 & 5 & 6 & 61 \\ \hline 1.& Алексей Волошин & 8 & 4 & 3 & 4 & 4 & 4 & 4 & 18 & 5 & 7 & 61 \\ \hline 3.& Сергей Половинкин & 8 & 4 & 5 & 2 & 0 & 5 & 11 & 11 & 5 & 7 & 57 \\ \hline 4.& Виктор Филимоненков & 0 & 0 & 5 & 4 & 4 & 4 & 0 & 0 & 5 & 0 & 22 \\ \hline 5.& Николай Дерюгин & 6 & 4 & 5 & 2 & 0 & 1 & 0 & 0 & 0 & 3 & 21 \\ \hline 6.& Дмитрий Пашуткин & 0 & 0 & 5 & 0 & 4 & 0 & 2 & 0 & 5 & 0 & 16 \\ \hline 7.& Эдвард Туркевич & 0 & 0 & 5 & 4 & 0 & 2 & 0 & 0 & 0 & 0 & 11 \\ \hline 8.& Евгений Машеров & 0 & 0 & 3 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 5 \\ \hline 9.& Mathusic & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ \hline 9.& Евгений Гужавин & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 3 & 4 \\ \hline \end{tabular}
====================================

Итоги тематического конкурса
\displaystyle \begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|} \hline & & КГ6 & КГ7 & КГ8 & КГ9 & КГ10 & \Sigma \\ \hline 1.& Анатолий Казмерчук & 8 & 4 & 2 & 12 & 12 & 38 \\ \hline 1.& Алексей Волошин & 8 & 4 & 4 & 4 & 18 & 38 \\ \hline 3.& Сергей Половинкин & 8 & 4 & 0 & 11 & 10 & 33 \\ \hline 4.& Николай Дерюгин & 6 & 4 & 0 & 0 & 0 & 10 \\ \hline 5.& Дмитрий Пашуткин & 0 & 0 & 4 & 2 & 0 & 6 \\ \hline 6.& Виктор Филимоненков & 0 & 0 & 4 & 0 & 0 & 4 \\ \hline \end{tabular}

[VAL]

Завершился 13-й тур Математического марафона

Упорную борьбу за победу в туре с начала до конца вели Анатолий Казмерчук, Алексей Волошин и Сергей Половинкин. В итоге ,Анатолий и Алексей разделили первое место, а вся троица далеко оторвалась от преследователей.
Виват лауреатам!

Произошли изменения и в общей таблице Марафона. Так, на самом финише Анатолий Казмерчук обошел Виктора Филимоненкова и вышел на общее второе место. Впрочем, Виктор совсем близко, и, полагаю, без борьбы не сдастся.

Положение лидирующей группы после 13-и туров
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|r|r|c|} \hline № & Участники & I & II & III & IV & V & VI & VII & VIII & IX & X & XI & XII & XIII & \Sigma\\ \hline 1. & Владислав Франк & - & - & 32 & 53 & 47 & 85 & 59 & 47 & 23 & 33 & - & 6 & - & 385\\ \hline 2. & Анатолий Казмерчук & - & - & - & - & - & - & - & 55 & 67 & - & 61 & 74 & 61 & 318\\ \hline 3. & Виктор Филимоненков & - & - & - & - & - & 77 & 64 & 60 & 7 & 21 & 32 & 32 & 22 & 315\\ \hline 4. & Олег Полубасов & - & - & - & - & 77 & - & 65 & 45 & 81 & - & - & - & - & 268\\ \hline 5. & Алексей Волошин & - & - & - & - & - & - & - & - & - & 45 & 20 & 72 & 61 & 198\\ \hline 6. & Сергей Половинкин & - & - & - & - & - & - & - & - & - & - & - & 80 & 57 & 137\\ \hline 7. & Николай Дерюгин & - & - & - & - & - & - & - & - & 18 & 3 & 30 & 49 & 21 & 121\\ \hline 8. & Андрей Богданов & - & - & - & - & 45 & - & 52 & 15 & - & - & - & - & - & 112\\ \hline 9. & Иван Козначеев & - & - & - & 53 & 2 & 13 & 8 & 9 & 3 & - & - & - & - & 88\\ \hline 10. & Борис Бух & 38 & 28 & 15 & - & - & - & - & - & - & - & - & - & - & 81\\ \hline \end{tabular}

[VAL]

Если Вы думаете, что Марафон впал в зимнюю спячку, то Вы ошиблись!
14-й тур на подходе. Объявляется готовность №1.
И не надейтесь встретить Новый Год без новых задач!

Рассчитываю на активное участие испытанных бойцов.
Надеюсь на пополнение марафонских рядов.

[Mathusic]

Что день грядущий нам готовит? Какая тема будет основная/её не будет?

[VAL]

Mathusic в сообщении #387960 писал(а):

Что день грядущий нам готовит? Какая тема будет основная/её не будет?

Будет. Математические игры и стратегии.

[VAL]

Поздравляю участников Марафона с Новым годом!

Пусть наступающий год принесет вам много поводов для радости и прочих положительных эмоций и как можно меньше поводов для злобы, обид, раздражения..
Желаю успехов во всех ваших благородных начинаниях и высоких устремлениях, включая, конечно же, Марафон!

PS: Тем, кто по недоразумению до сих пор не присоединился к Марафону, желаю в наступающем году исправить эту оплошность. Тем более, что в ознаменование простого года ведущие подобрали для очередного тура столь же простые задачи.

[General]

Поздравляю участников с Новым Годом!

Некоторые уточнения в условиях задач

Задача ММ133:
Вместо "Выигрывает тот, кто забирает последнюю спичку" следует читать "Проигрывает тот, у кого нет возможности сделать очередной ход согласно правилам"

Задача ММ137:
Т.к. начальные скорости шашек равны 1, то на первом ходу у каждого игрока есть выбор: передвинуть шашку на 1 клетку или же увеличить её скорость и передвинуть уже на 2 клетки

Задача ММ139:
Игра заканчивается, когда после очередного действия на индикаторе появится некоторое наперёд заданное число N (N>10). Если же некоторым ходом получено число, более N, игрок, сделавший такой ход, проигрывает.

[VAL]

General в сообщении #395700 писал(а):

Поздравляю участников с Новым Годом!

А я поздравляю участников с Рождеством!

Цитата:

Некоторые уточнения в условиях задач

В ММ140 n, конечно же, больше 1.

[VAL]

====================================

ММ131 (3 балла) (Прощай 2010-й)

Граф $G=\left<V,E\right>$ задан на множестве $V = \{1, 2,\dots, 2010\}$ по правилу: $\{x,y\} \in E \Leftrightarrow x+y = a \vee x+y = b$, где $a$ и $b$ - фиксированные натуральные числа.
При каких $a$ и $b$, граф $G$:
а) связен;
б) является деревом;
в) является цепью;
г) имеет циклы?

====================================

Решение

Ребро ${x,y}$ такое, что $x+y = a$ будем называть a-ребром, иначе b-ребром.
Ясно, что степень каждой вершины не больше 2, поскольку ей инцидентны не более одного ребра каждого типа.
При $a = b$ степени вершин G не больше 1. Такие графы не могу удовлетворять условиям пунктов а-г. Поэтому можно считать, $a$ и $b$ различны.
Допустим, что в графе есть циклы и вершина $x$ - наибольшая (в смысле сравнения натуральных чисел) в одном из циклов. Cмежные ей вершины - $a-x$ и $b-x$. А этим вершинам, кроме $x$, смежны вершины $b-a+x$ и $a-b+x$. Ясно. что одно из этих чисел больше $x$, что противоречит выбору $x$. Значит, G не имеет циклов ни при каких $a$ и $b$.
Для графа, степени вершин которого не превосходят 2, и не имеющего циклов, условия пунктов a-в равносильны. Для того, чтобы каждое из них выполнялось необходимо и достаточно, чтобы в G было 2009 ребер.
Легко видеть. что количество a-ребер в G равно $m(a)=1005-\left\lceil \frac{|2011-a|}{2}\right\rceil$. Ясно,что $m(a)\le 1005$ и максимум достигается лишь при $a = 2011$. Значение 1004 досгитается при $$a\in \{2009, 2010, 2012, 2013\}$
Аналогичные соотношения имеют место для b-ребер.
Поэтому общее число ребер $m=m(a)+m(b)$ может достигать 2009 только тогда, когда одно $a$, $b$ равно 2011. а другое отлчается от него не более чем на 2.

Ответ: Граф G связен, является деревом, является цепью тогда и только тогда. когда ровно одно из чисел $a, b$ равно 2011, другое отличется от 2011 не более чем на 2. Граф G не содержит циклов ни при каких $a$ и $b$.


Обсуждение

Как и в предыдущих марафонских задачах под графом я понимал классичиеский граф, в частности, не имеющий петель.
Нкоторые участники допускали наличие петель и получили несколько иные ответы. Их решения я считал верными. Самые предусмотрительные рассмотрели оба случая :)

Получаемые при подходящих a и b цепи можно выписать явно:
{a, b} = {2009, 2011}: 2009-2-2007-4-2005-6-...-3-2008-1-2010;
{a, b} = {2010, 2011}: 1005-1006-1004-1007-1003-...-2008-2-2009-1-2010;
{a, b} = {2011, 2012}: 1-2010-2-2009-3-2008-...-508-504-507-505-506;
{a, b} = {2011, 2013}: 1-2010-3-1008-5-...-6-2007-4-2009-2.

Разумеется, задача легко обобщается на граф с произвольным количеством вершин n.
При четных n (больших 2) для выполнения условий пунктов а-в одно из чисел a, b должно быть равно n+1, а другое отличаться от первого не более, чем на 2.
При нечетных n (больших 1) - a и b должны быть, двумя элементами множества {n, n+1, n+2}.

Награды

За правильное решение задачи Сергей Половинкин, Владислав Франк, Алексей Волошин. Евгений Гужавин, Анатолий Казмерчук и Дмитрий Пашуткин получают по 3 призовых балла, а Александр Ларин - 2 призовых балла.

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

====================================

Разбор задачи ММ131 подготовил Владимир Лецко

[VAL]

======= 132 ========

ММ132 (5 баллов) (Здравствуй 2011-й)

$G=\left<V,E\right>$ задан на множестве $V = \{1, 2,\dots, 2011\}$ по правилу: $\{x,y\} \in E \Leftrightarrow |x-y| > a $, где $a$ - фиксированное натуральное число, меньшее 1006.
Сколько периферийных вершин может иметь граф G?

Примечание: Вершина графа называется периферийной, если ее эксцентриситет равен диаметру графа.

====================================

Решение

Рассмотрим три случая.

1. $а=1005$.
В этом случае граф не связен и, следовательно, не имеет периферийных вершин.

2. $670\le a\le 1005$.
В этом случае диаметр графа равен 3.
Вершины эксцентриситета 3 будут сосредоточены на двух промежутках $[2011-2a,\dots, a+1]$ и $[2011-a, \dots, 2a+1]$.
Например, кратчайший путь из вершины $2011-2a$ в вершину $2011-a$ будет таким: $2011-2a \to 2011 \to 1 \to 2011-a$.
В то же время:
от вершин из промежутка $[1, \dots, 2011-2a]$ до любой вершины можно добраться либо за один шаг, либо через вершину $2011$;
аналогично не более чем за два шага можно добраться до любой вершины от вершин из промежутка $[2a+2, \dots, 2011]$.
Наконец, от вершин из промежутка $[a+2, \dots, 2010-a]$ можно добраться не более чем за два шага до любой вершины (через вершину $1$ до вершин с бОльшими номерами и через вершину $2011$ до вершин с меньшими номерами).
Таким образом, количество периферийный вершин равно $(a+2-(2011-2a))+(2a+2-(2011-a))=6a-4018$.
При значениях $a$ из рассматриваемого диапазона это дает нам следующий набор допустимых количеств периферийных вершин: $2,8,14,\dots, 2006$.

3. $a<670$
В этом случае каждая вершина имеет эксцентриситет 2. Поэтому все 2011 вершин будут периферийными.

Ответ:: $2, 8, 14, 20\dots, 2000, 2006, 2011$ (или ни одной).


Обсуждение

К моему удивлению, серьезные разногласия и путаницу вызвал случай $a=1005$.
Полагаю, кроме варианта, приведенного в решении, имеет право на существование и такой: поскольку граф не связен, эксцентриситет каждой вершины бесконечен и все вершины являются периферийными.
Каким образом некоторые участники смогли насчитать 2008, 2010 или и вовсе одну периферийную вершину - для меня загадка.

Марафонцы существенно разошлись во мнениях, давая эстетическую оценку задаче ММ132. Для меня задачка любопытна немного неожиданным расположением периферийных вершин в $G$ с точки зрения обычной упорядоченности вершин: и не по краям, и не в серединке.


Награды

За решение задачи ММ132 Сергей Половинкин и Александр Ларин получают по 5 призовых баллов, Алексей Волошин и Анатолий Казмерчук - по 4 призовых балла, Дмитрий Пашуткин - 3 призовых балла, а Евгений Гужавин - 2 призовых балла.


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

====================================

Разбор задачи ММ132 подготовил Владимир Лецко

[VAL]

General писал(а):

======= 133 ========
ММ133 (3 балла)

На столе лежит N спичек. Петя и Вася поочерёдно берут оттуда от 1 до 5 спичек, однако нельзя повторять число, взятое соперником на предыдущем ходу. Выигрывает тот, кто забирает последнюю спичку. Начинает Петя, своим первым ходом может взять любое количество от 1 до 5. Найдите общий вид чисел N, при которых партию выиграет Вася.
====================================

Решение

Эта игра отличается от классической игры Баше тем, что позицию в ней можно однозначно определить не одинм, а парой чисел: (N, M), где N - число спичек, оставшееся на столе, а M - число спичек, взятое на предыдущем ходу. Тогда из позиции (N, M) игрок своим ходом может получить все позиции вида (N-K, K), для которых $K\neq M,~K<N$.

Построим и начнём заполнять таблицу выигрышных/проигрышных позиций:


Т.к. тот игрок, чья очередь хода наступит, когда стол опустел, проиграл, то весь нулевой столбец состоит из проигрышных позиций.

Найдём позиции, из которых можно одним ходом поставить противника в проигрышную позицию:


Выигрышными будут все позиции столбцов 1-5, кроме позиций вида (N,N).

Далее, из позиции (1,1) сделать ход согласно правилам невозможно, и она проигрышна. Тогда позиция (2,2) - выигрышна, т.к. из неё можно, взяв одну спичку, попасть в (1,1) и заставить проиграть соперника. Остальные позиции этой диагонали - проигрышные, т.к. все ходы из них ведут в ввыигрышные позиции.


Продолжая поочерёдно находить выигрышные и проигрышные позиции определяем, что в столбце 6 проигрышна только (6,3), а в столбце 7 - все позиции проигрышны, т.е., при старте с 7 спичек второй игрок выиграет. Далее получаем такую картину:


Замечаем, что столбцы 22-26 повторяют столбцы 9-13. Т.к. значение, стоящее в ячейке полностью определяется значениями ячеек в предыдущих пяти столбцах, то сформировался период и полностью из нулей будут состоять столбцы вида 13k и 13k+7


Обсуждение

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

Некоторым участникам помешало набрать максимальное количество баллов то, что они заметили периодичность, но неверно определили её характер.

Награды
За правильное решение задачи Сергей Половинкин, Анатолий Казмерчук, Алексей Волошин, Владислав Франк, Евгений Гужавин и Александр Ларин получают по 3 призовых балла.
Дмитрий Пашуткин и Николай Дерюгин получают по 1 призовому баллу.

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

====================================

Разбор задачи ММ133 подготовил Алексей Извалов.

[VAL]

Срок приема решений задачи ММ134 продлен до 31.01.11

[VAL]

Текущее положение участников
в XIV туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& 131 & 132 & 133 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 5 & 3 & 11 \\ \hline 2.& Алексей Волошин & 3 & 4 & 3 & 10 \\ \hline 2.& Анатолий Казмерчук & 3 & 4 & 3 & 10 \\ \hline 2.& Александр Ларин & 2 & 5 & 3 & 10 \\ \hline 5.& Евгений Гужавин & 3 & 2 & 3 & 8 \\ \hline 6.& Дмитрий Пашуткин & 3 & 3 & 1 & 7 \\ \hline 7.& Владислав Франк & 3 & - & 3 & 6 \\ \hline 8.& Николай Дерюгин & - & - & 1 & 1 \\ \hline \end{tabular}$

[VAL]

==================== 134 ===============

ММ134 (МИ2) (4 балла)

Позицией в игре является конечное множество чисел, записанных в двоичной системе счисления. Игроки по очереди разбивают одно из чисел этого множества на части так, чтобы выполнялись два правила:
1) оба полученных числа должны начинаться с единицы;
2) хотя бы одно из них должно заканчиваться нулём.
Например, 1101 можно разбить только на 110 и 1, а 11010 - на 1 и 1010 или на 110 и 10.

Проигрывает тот игрок, кто не сможет сделать ход согласно правилам.

Кто выиграет, если игра начнётся с числа с числа (2011)_{10}=(11111011011)_2?


Решение.

Выигрывает 2-ой игрок.
Приведём решение Сергея Половинкина.

На первом ходу у 1-ого участника есть всего 2 хода:

1) (11111011011) разбивает на $111110$ и $11011$
Тогда у 2-ого игрока есть 5 возможных ходов, но 4 из них проигрывают, к выигрышу ведет только разбиение $111110$ на $1111$ и $10$. Тогда у 1-ого единственный ход - разбить $11011$ на $110$ и $11$, после этого 2-ой тоже выполняет единственный ход, разбивает $110$ на $1$ и $10$, получаем множество чисел $1111$, $10$, $1$, $10$ и $11$, у 1-ого ходов нет.

2) (11111011011) разбивает на $111110110$ и $11$
Тогда у 2-ого игрока есть 6 возможных ходов, но 4 из них проигрывают, к выигрышу ведет разбиение $111110110$ на $1111$ и $10110$. Но проще выигрывает разбиение $111110110$ на $1111101$ и $10$. Тогда все форсированно: 1-ый делает единственный ход, разбивает $1111101$ на $111110$ и $1$, тогда 2-ой разбивает $111110$ на $1111$ и $10$ и выигрывает.

Обсуждение

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

Участники справились с данной задачей, а некоторые заметили её связь с играми Гранди или Ним и предприняли некоторые шаги к обобщению. Это награждалось дополнительными баллами. Можно сказать, что в постоянно пополняемом после каждого марафона списке задач, ждущих своего развития, появился новый элемент :)


Награды

За правильное решение задачи Владислав Франк, Алексей Волошин, Александр Ларин и Анатолий Казмерчук и получают по 4 балла. За развитие темы Николай Дерюгин, Евгений Гужавин и Сергей Половинкин получают по 4+2=6 баллов.


Эстетическая оценка задачи 4,3
======================================

Разбор задачи ММ134 подготовил Алексей Извалов

======================================

Текущее положение участников
в XIV туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|} \hline №& Участники& 131 & 132 & 133 & 134 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 5 & 3 & 6 & 17 \\ \hline 2.& Алексей Волошин & 3 & 4 & 3 & 4 & 14 \\ \hline 2.& Анатолий Казмерчук & 3 & 4 & 3 & 4 & 14 \\ \hline 2.& Александр Ларин & 2 & 5 & 3 & 4 & 14 \\ \hline 2.& Евгений Гужавин & 3 & 2 & 3 & 6 & 14 \\ \hline 6.& Владислав Франк & 3 & - & 3 & 4 & 10 \\ \hline 7.& Дмитрий Пашуткин & 3 & 3 & 1 & - & 7 \\ \hline 7.& Николай Дерюгин & - & - & 1 & 6 & 7 \\ \hline \end{tabular}

[VAL]

======= 135 ========

ММ135 (4 балла)

Конечно ли множество пар натуральных чисел $(a,b)$, таких что остатки от деления $a^2$ на $b$ и $b^2$ на $a$ равны по 2011?

===============

Решение

Положим: $a_1=3234, \ a_2=8467, \ a_{i+1}=3a_i-a_{i-1}$.
Легко проверяется и доказывается по индукции, что для любых трех соседних членов этой последовательности выполняется соотношение $a_i^2=a_{i-1}a_{i+1}+2011$, из которого следует, что любую пару соседних членов можно взять в качестве требуемых a и b.

Ответ: бесконечно.


Обсуждение

Существует много (возможно, бесконечно много) последовательностей, соседние члены которых будут подхoдящими парами. Например:

$a_1=2054, \ a_2=18255, \ a_{i+1}=9a_i-a_{i-1}$;
$a_1=2090, \ a_2=47979, \ a_{i+1}=23a_i-a_{i-1}$;
$a_1=2181, \ a_2=10450, \ a_{i+1}=5a_i-a_{i-1}$;
$a_1=2545, \ a_2=12194, \ a_{i+1}=5a_i-a_{i-1}$;
$a_1=3115, \ a_2=40254, \ a_{i+1}=13a_i-a_{i-1}$;
$a_1=4298, \ a_2=29459, \ a_{i+1}=7a_i-a_{i-1}$;
$a_1=4925, \ a_2=12894, \ a_{i+1}=3a_i-a_{i-1}$.

Кроме того, существует много подходящих пар, в которых a и b не взаимно просты (разумеется, их НОД равняется 2011). Например, $(4022, 6033)$ или $(19\cdot 2011, 17285\cdot 2011)$. Но мне не удалось построить из таких пар какую-либо бесконечную серию.

Владислав Франк в качестве бесконечного множества подходящих пар использовал множество решений диофантова уравнения $a^2+b^2-2011=37ab$. А решение этого уравнения свел к решению обобщенного уравнения Пелля $x^2-1365y^2=8044$.

Разумеется, 2011 не является исключительным числом в смысле нашей задачи. Пусть $m>3$. Положив $a_1=m^2-3m+1, \ a_2=m^3-5m^2+6m-1, \ a_{i+1}=(m-2)a_i-a_{i-1}$, получим бесконечно много пар (соседних членов последовательности) таких, что остатки от деления $a_i^2$ на $a_{i+1}$ и $a_{i+1}^2$ на $a_i$ равны $m$.
Сергей Половинкин заметил, что члены последней последовательности - это в точности значения чебышевских полиномов второго рода с четными номерами при $x=\frac{\sqrt{m}}2$.

При $m<4$ указанный метод уже не приводит к возрастающей последовательности натуральных чисел и не дает подходящих пар.
Однако, бесконечность подходящих пар для $m=1$ очевидна. Достаточно рассматривать пары соседних чисел. Более обще, если $m=s^2$, то при $a>m$ пара $(a,a+s)$ будет подходящей.

Остаются два последних вопроса: Существуют ли подходящие пары для $m=2$ и $m=3$. И если существуют, то конечно ли их число?
Ответ на первый вопрос положителен. Для $m=3$ подходящими парами являются, например, (6, 33), (39, 69), (426, 753), (498, 19077), (789, 27066), (4647, 8214).
Для $m=2$ мне удалось подобрать всего одну пару (94, 1262).
Таким образом, ответ на второй вопрос остается открытым.

Награды

К моему удивлению, с задачей ММ135 справились всего трое участников Марафона.
За правилное решение и обобщение задачи ММ135 Сергей Половинкин получает 7 призовых баллов. Владислав Франк и Алексей Волошин получают по 4 призовых балла.

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

===============

Обзор задачи ММ135 подготовил Владимир Лецко