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

VAL · 27/06/08 4065 Волгоград

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

VAL · 27/06/08 4065 Волгоград

Вопрос, оставшийся открытым при разборе задачи ММ135, решен:

Dm13 писал(а):

VAL писал(а):

А между тем при разборе ММ135, например, возникли интересные вещи. Я имею ввиду ситуацию с $m=2$ . Кто что про это думает?

А как же второй вопрос для $m=3$ ?
Для его решения рассмотрим уравнение
$3a^2+3b^2-7ab-9=0$
и воспользуемся замечательным онлайн солвером диофантовых уравнений http://www.alpertron.com.ar/QUAD.HTM , который дает бесконечную возрастающую серию решений:
$a_0=6$ , $b_0=3$ ;
$a_{n+1}=16a_n-9b_n$
$b_{n+1}=9a_n-5b_n$ .
Из исходного уравнения получаем:
$a_n^2=(\frac{7}{3}a_n-b_n)b_n+3$ ,
$b_n^2=(\frac{7}{3}b_n-a_n)a_n+3$ .

Заметим, что все $a_n$ и $b_n$ делятся на 3. Тогда $\frac{7}{3} a_n-b_n$ и $\frac{7}{3} b_n-a_n$ целые. Тогда при $n>0$ получаем бесконечную серию пар $a_n,b_n$ , удовлетворяющих условию задачи при $m=3$ .

-----------------------------------------------

Для $m=2$ по аналогии рассмотрим уравнение:
$2a^2+2b^2-27ab-4=0$ .
Получим бесконечную возрастающую серию решений (Верность, признаюсь, не проверял. Доверился солверу :) ):
$a_0=1262$ , $b_0=94$ ;
$a_{n+1}=10 631719a_n-791904b_n$
$b_{n+1}=791904a_n-58985b_n$ .

Перепишем исходное уравнение в виде:
$a_n^2=(\frac{27}{2}a_n-b_n)b_n+2$ ,
$b_n^2=(\frac{27}{2}b_n-a_n)a_n+2$ .

Так как $a_n$ и $b_n$ делятся на 2, то $\frac{27}{2} a_n-b_n$ и $\frac{27}{2} b_n-a_n$ - целые. Получаем бесконечную серию пар $a_n,b_n$ , удовлетворяющих условию задачи при $m=2$ .

За ценный "довесок" к ММ135 Дмитрий Пашуткин получает 4 призовых балла (они уже отражены в последней опубликованной таблице промежуточных результатов).

VAL · 27/06/08 4065 Волгоград

======= 136 ========

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

ММ136 (МИ3) (5 баллов)

На столе в открытую лежит 16 карт: 4 туза (считаются за 1 очко), 4 двойки, 4 тройки и 4 четвёрки. Петя и Вася по очереди берут оттуда по одной карте и складывают в отдельную стопку (общую). Выигрывает тот, после чьего хода сумма очков в этой стопке составит 21 очко (или заставивший соперника своим ходом превысить это значение). Петя начинает игру. Кто победит в игре и какой стратегии он должен придерживаться (как реагировать на ходы соперника)?

Решение

Позиция в данной игре записывается четвёркой чисел (a,b,c,d), каждое из которых не больше четырёх и которые представляют количества взятых, соответстсвенно, тузов, двоек, троек и четвёрок. Таким образом, всё множество позиций можно организовать в виде 4-мерного гиперкуба 5х5х5х5 и ходом увеличение одного из индексов текущей ячейки на единицу.

Для того, чтобы проанализировать эту игру, неплохо бы как-то разложить этот гиперкуб на плоскость. Это можно сделать в виде такой таблицы, состоящей из 25-ти секторов. Тогда взятие единицы или двойки соответствует сдвигу вниз или влево в пределах одного сектора, а взятие тройки или четвёрки - смене сектора на нижний или правый.

$Изображение$

В позициях, соответствующих перебору, стоят единицы, ведь игрок, пришедший в них, проиграл, значит тот, к кому в данный момент перешла очередь хода - выиграл. В позициях, где сумма a+2b+3c+4d=21, стоят нули, т.к. пришедший туда выигрывает, значит, тот, кому очередь ход перешла, проиграл. Остальные ячейки заполняем рекурсивно по правилу: Если из ячейки можно хотя
одним ходом попасть в проигрышную, она - выигрышная, а если же все ходы ведут в выигрышные позиции, она - проигрышная.

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

Обсуждение

Как оказалось, задачу можно успешно решить и без построения данной таблицы. Большинство участников использовали принцип дополнения суммы до числа, дающего остаток 1 при делении на 5, с некоторыми оговорками, обусловленными ограниченностью количества карт.
Кратко правило формулируется так: на первом ходу Петя берет 3, а затем, он должен оставить число, дающее остаток 1 при делении на 5, а если это невозможно, то число, дающее остаток 3.

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

Награды

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

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

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

-- 10 фев 2011, 18:17 --

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

VAL · 27/06/08 4065 Волгоград

======= 137 ========

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

ММ137 (МИ4) (6 баллов)

Шашки двух игроков стоят на противоположный полях прямоугольника 1x(N+2), между ними N клеток. Начальная скорость каждой шашки равна 1.
Каждый ходом игрок может или передвинуть свою шашку в сторону противника на величину, равную текущей скорости или увеличить скорость на 1 и передвинуть шашку в этом направлении уже на величину увеличенной скорости.
Выигрывает тот, кто поставит свою шашку на шашку противника или перепрыгнет через неё.
Для каких натуральных N, не превосходящих 100, выиграет второй игрок?

Решение

В данной игре позиция описывается тройкой чисел: текущее расстояние n, скорость фишки ходящего игрока v и его соперника w. Из позиции (n,v,w) можно попасть в (n-v,w,v) и в (n-v-1,w,v+1).

Таким образом, несложно организовать перебор даже в Excel'e и выяснить, что для значений v = w = 1 проигрышными будут позиции с n = 2, 6, 8, 11, 13, 17, 20, 24, 27, 29, 32, 36, 38, 41, 45, 47, 51, 53, 56, 58, 62, 64, 67, 70, 74, 76, 80, 83, 87, 89, 93, 96, 98

Осуждение

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

Награды

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

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

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

VAL · 27/06/08 4065 Волгоград

Срок приема решений ММ138 продлен до 21.02.11

-- 17 фев 2011, 18:48 --

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

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

Petr6085 · 17/02/11 7

a в ММ137 для каких натуральных N, не превосходящих 300, выиграет второй игрок, можете сказать?

-- Чт фев 17, 2011 22:27:48 --

или, лучше, можете файл Excel выложить с перебором? А то я не совсем понял разбор...

General · 17/05/08 358 Анк-Морпорк

ОК, я сделаю до 300 (тогда максимальный разгон будет равен 24) и выложу.

Petr6085 · 17/02/11 7

Cпасибо, жду!

VAL · 27/06/08 4065 Волгоград

VAL в сообщении #414063 писал(а):

Срок приема решений ММ138 продлен до 21.02.11

И еще раз продлен. До 25.02.11
Во-первых, по просьбам ряда участников.
Во-вторых (а на самом деле во-первых) из-за продолжающегося цейтнота у ведущего.

General · 17/05/08 358 Анк-Морпорк

Да-да, спасибо большое, что продляете, у меня ту сначала на работе конкурс среди диспетчеров надо было провести, потом контрольная МАН, защита работ - но к 25му успею разобрать.

VAL · 27/06/08 4065 Волгоград

======= 138 ========

ММ138 (6 баллов)

Доказать, что для любого натурального k найдутся натуральные a, n и g, такие что для всех i из {0,1,... ,k-1}
в системе счисления с основанием g+i, число a является n-i-значным.

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

Решение

Приведу решение Владислава Франка.

Условие задачи равносильно следующему утверждению: $\forall i \in \{0,1,\dots,k\} (g+i)^{n-i}> a\ge (g+i)^{n-i-1}$
Попробуем подобрать $g$ и $n$ так, чтобы все выражения в левых (и правых) частях неравенства были очень близки друг к другу.
Для этого нужно, чтобы функция $f(x)=(g+x)^{n-x}$ была почти постоянна, а для этого ее производная $f'(x)=(g+x)^{n-x}\cdot \left(\frac{n-x}{g+x}-\ln(g+x)\right)$ должна мало отличаться от нуля.
Для этого $n$ должно быть близко к $g\ln g$ . Выберем $g$ и в качестве $n$ возьмем $\lceil g\ln g\rceil$ .
Тогда $\frac{n-x}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$ . Значит функция убывает и принимает максимальное значение на границе интервала. Поэтому от всех оценок для $a$ сверху достаточно оставить одну: $(g+k)^{n-k}>a$ .
Аналогично, рассматривая нижние оценки, получаем: $h'(x)=(g+x)^{n-x-1}\cdot \left(\frac{n-x-1}{g+x}-\ln(g+x)\right)$ и $\frac{n-x-1}{g+x}-\ln(g+x) \lt \frac 1{g+x}(n-g\ln g) < 0$ .
Поэтому из всех оценок снизу достаточно взять $a\ge g^{n-1}$ .

Докажем, что при больших $g$ в интервале $\left(g^{n-1},(g+k)^{n-k}\right)$ найдется хотя бы одно натуральное число (оно-то и будет нашим $a$ ).
(Заодно мы докажем, что верхняя граница интервала действительно больше нижней.)
Достаточно доказать неравенство $(g+k)^{n-k}> 2g^{n-1}$ . Тогда длина интервала будет велика и хотя бы одно число туда попадет.
Логарифмируем: $(n-k)\ln (g+k) > (n-1)\ln g +\ln 2$
$\left[g\ln g\right](\ln(g+k)-\ln g)-k\ln(g+k)+\ln g -\ln 2 > 0$
$\left[g\ln g\right](\ln(1+\frac{k}{g})-k\ln(g+k)+\ln g -\ln 2 > 0$
Как известно, $\ln(1+x) > x-\frac{x^2}{2}$ при малых $x$ , поэтому достатчно будет доказать
$(g\ln g -1)\left(\frac{k}{g}-\frac{k^2}{2g^2}\right)-k\ln(g+k)+\ln g - \ln 2 > 0$
$\ln g \left(k-\frac{k^2}{2g}\right)-k\ln(g+k)+\ln g > \ln 2 + \frac{k}{g}-\frac{k^2}{2g^2}$
$\ln g > \ln 2 +\frac{k}{g}-\frac{k^2}{2g^2}+\frac{k^2\ln g}{2g}+k\ln(1+\frac{k}{g})$
Очевидно, это верно при больших $g$ поскольку в правой части все слагаемые, кроме первого, стремятся к 0 с ростом $g$ .
Остается взять подходящее $g$ , по нему $n$ и по ним $a$ .

Обсуждение

Приведу пример для $k=5$ : Пусть $a=3486784400$ (в десятичной системе). Ниже приводится (обратная) запись $a$ для систем с основаниями от 5 до 9:

Код:

         5, [0, 0, 1, 0, 0, 1, 4, 0, 1, 0, 2, 1, 4, 2], 14

            6, [2, 1, 2, 0, 2, 5, 3, 5, 5, 3, 3, 3, 1], 13

             7, [1, 2, 1, 5, 1, 1, 6, 5, 2, 2, 5, 1], 12

               8, [0, 2, 6, 5, 1, 0, 5, 6, 7, 1, 3], 11

                9, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8], 10

Для больших значений $k$ потребуются огромные $g$ . Например, для $k=16$ Сергей Половинкин нашел $a$ порядка $10^{273}$ . Похожие оценки получил и Алексей Волошин.

Награды

За правильное (более аккуратное, чем у ведущего) решение задачи ММ138 Дмитрий Пашуткин, Анатолий Казмерчук и Владислав Франк получают по 7 призовых баллов. Александр Ларин получает 6 призовых баллов, Алексей Волошин и Сергей Половинкин - по 4 призовых балла, Николай Дерюгин - 3 призовых балла.

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

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

VAL · 27/06/08 4065 Волгоград

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

VAL · 27/06/08 4065 Волгоград

======= 139 ========

Задача ММ139 является развитием идеи задачи Кузнецова Сергея Тихоновича.
Оценка за решение этой задачи будет учитываться дважды: в основном Марафоне и в тематическом конкурсе.

ММ139 (МИ5) (7 баллов)

Кнопки калькулятора расположены так, как на цифровой клавиатуре:
$\begin{tabular}{|c|c|c|} \hline 7 & 8 & 9 \\ \hline 4 & 5 & 6 \\ \hline 1 & 2 & 3 \\ \hline \multicolumn{2}{|c|}{0}\\ \cline{1-2} \end{tabular}$
Назовём смежными те кнопки, которые имеют общую сторону или отрезок стороны (клавиша 0 смежна с клавишами 1 и 2).
Вначале на индикаторе число 0. Начинает игру Петя, прибавляя к нему любое (им выбранное) число от 0 до 9. Затем Вася прибавляет в полученному числу слагаемое, находящееся на смежной кнопке с той, которую нажимал Петя. Затем Петя делает свой ход, прибавляя число, смежное с нажатым Васей и т.д. Игра заканчивается, когда после очередного действия на индикаторе появится некоторое наперёд заданное число N (N>10). Если же некоторым ходом получено число, более N, игрок, сделавший такой ход, проигрывает.
Для каких N наибольшее число вариантов первого хода Пети приведёт его в дальнейшем к победе?

Решение
Для удобства построений переформулируем правила игры так: начинаем с некоторого N>10, и отнимаем от него числа от 0 до 9, пока не получится 0. Игрок, вынужденный получить отрицательное число, проигрывает.

Тогда из позиции (N,k) можно попасть во все позиции (N-d, d), где d - число на кнопке, смежной с k. Вот
список выигрышных и проигрышных позиций.

Таким образом, при N=43 или N=52 по 6 первых ходов Пети приведут его в дальнейшем к победе. Из остальных начальных позиций, больших десяти, таких ходов меньше.

Обсуждение
Учатники Марафона также заметили, что для всех N>2 существует универсальная выигрышная стратегия - нажимать на клавишу 0 до тех пор, пока не удастся закончить партию одним ходом или заставить противника следующим ходом сделать перебор.

Награды
За правильное решение задачи анатолий Казмерчук, Дмитрий Пашуткин, Алексей Волошин и Сергей Половинкин получают по 7 призовых баллов. Кирилл Веденский, решавший несколько другую задачу (когда только Пете нужно для победы получить N, а Васе - получить число, большее N), получает 6 баллов.

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

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

VAL · 27/06/08 4065 Волгоград

Текущее положение участников в XIV туре Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 131 & 132 & 133 & 134 & 135 & 136 & 137 & 138 & 139 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 5 & 3 & 6 & 7 & 7 & 6 & 4 & 7 & 48 \\ \hline 2.& Алексей Волошин & 3 & 4 & 3 & 4 & 4 & 5 & 6 & 4 & 7 & 40 \\ \hline 3.& Анатолий Казмерчук & 3 & 4 & 3 & 4 & - & 5 & 6 & 7 & 7 & 39 \\ \hline 4.& Дмитрий Пашуткин & 3 & 3 & 1 & - & 4 & 5 & 6 & 7 & 7 & 36 \\ \hline 5.& Александр Ларин & 2 & 5 & 3 & 4 & - & 5 & 6 & 6 & - & 31 \\ \hline 6.& Владислав Франк & 3 & - & 3 & 4 & 4 & 5 & - & 7 & - & 26 \\ \hline 7.& Евгений Гужавин & 3 & 2 & 3 & 6 & - & 5 & 6 & - & - & 25 \\ \hline 8.& Кирилл Веденский & - & - & - & - & - & 5 & 6 & - & 6 & 17 \\ \hline 9.& Николай Дерюгин & - & - & 1 & 6 & - & 3 & - & 3 & - & 13 \\ \hline \end{tabular}$
==================================
Итоговое положение участников в темтическом конкурсе
XIV тура Математического марафона
$\begin{tabular}{|l|l|r|r|r|r|r|r|r|} \hline №& Участники & МИ1 & МИ2 & МИ3 & МИ4 & МИ5 & \Sigma \\ \hline 1.& Сергей Половинкин & 3 & 6 & 7 & 6 & 7 & 29 \\ \hline 2.& Алексей Волошин & 3 & 4 & 5 & 6 & 7 & 25 \\ \hline 2.& Анатолий Казмерчук & 3 & 4 & 5 & 6 & 7 & 25 \\ \hline 4.& Евгений Гужавин & 3 & 6 & 5 & 6 & - & 20 \\ \hline 5.& Дмитрий Пашуткин & 1 & - & 5 & 6 & 7 & 19 \\ \hline 6.& Александр Ларин & 3 & 4 & 5 & 6 & - & 18 \\ \hline 7.& Кирилл Веденский & - & - & 5 & 6 & 6 & 17 \\ \hline 8.& Владислав Франк & 3 & 4 & 5 & - & - & 12 \\ \hline 9.& Николай Дерюгин & 1 & 6 & 3 & - & - & 10 \\ \hline \end{tabular}$

VAL · 27/06/08 4065 Волгоград

Прием решений задачи ММ140 продлен до 9.03.11

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

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

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