Задача №15479

Из пары натуральных чисел $(a;b)$ за один ход можно получить пару $(a+2;b-1)$ или $(a-1;b+2)$ при условии, что оба числа в новой паре положительны. Сначала есть пара $(5;7)\text{.}$
а) Можно ли за 50 таких ходов получить пару, в которой одно из чисел равно 100?

б) За какое число ходов получится пара, сумма чисел в которой равна 400?

в) Какое наибольшее число ходов можно сделать так, чтобы после каждого хода оба числа в паре не превосходили 100?

а) Заметим, что при каждом ходе сумма чисел увеличивается на 1: при ходе $(a+2;b-1)$ сумма становится $(a+2)+(b-1)=a+b+1\text{,}$ при ходе $(a-1;b+2)$ сумма становится $(a-1)+(b+2)=a+b+1\text{.}$ Начальная сумма $5+7=12\text{.}$ После 50 ходов сумма станет $12+50=62\text{.}$ Если одно из чисел равно 100, то второе равно $62-100=-38\text{,}$ что не является натуральным (положительным) числом. Значит, получить такую пару за 50 ходов нельзя.

б) Пусть сделано $k$ ходов. Тогда сумма чисел станет $12+k\text{.}$ Чтобы сумма стала 400, нужно $12+k=400\text{,}$ откуда $k=388\text{.}$ Покажем, что 388 ходов можно сделать, сохраняя положительность чисел на каждом шаге. Используем стратегию: на каждом шаге увеличиваем меньшее из чисел (при равенстве увеличиваем любо

е). Докажем по индукции, что при такой стратегии после $k$ ходов оба числа положительны и сумма равна $12+k\text{.}$ Для $k=0$ это верно: $(5;7)\text{.}$ Шаг индукции: пусть после $k$ ходов числа $a>0$ и $b>0\text{,}$ сумма $a+b=12+k\text{.}$ Если $a⩽b\text{,}$ делаем ход $(a+2;b-1)\text{.}$ Тогда новые числа: $a^{\prime }=a+2>0\text{,}$ $b^{\prime }=b-1\text{.}$ Поскольку $a+b=12+k\text{,}$ то $b⩾a>0\text{,}$ и если $b=1\text{,}$ то $a=1$ (так как $a⩽b$), но тогда сумма $a+b=2\text{,}$ что при $k$ таком, что $12+k=2\text{,}$ т.е. $k=-10\text{,}$ невозможно. В общем случае, поскольку сумма растёт, $b$ остаётся положительным. Аналогично для случая $b<a\text{.}$ Таким образом, стратегия сохраняет положительность. Для $k=388$ сумма станет 400, и числа положительны. Меньшим числом ходов сумму 400 получить нельзя, так как сумма увеличивается только на 1 за ход. Следовательно, минимальное число ходов — 388.

в) Введём инварианты. Пусть после $k$ ходов числа равны $a$ и $b\text{.}$ Сумма $S=a+b=12+k$ (как в пунктах а и

б). Разность $D=a-b\text{.}$ Начальная разность $D_0=5-7=-2\text{.}$ Каждый ход изменяет разность: при ходе $(a+2;b-1)$ разность становится $(a+2)-(b-1)=a-b+3\text{,}$ т.е. увеличивается на 3; при ходе $(a-1;b+2)$ разность становится $(a-1)-(b+2)=a-b-3\text{,}$ т.е. уменьшается на 3. Следовательно, разность всегда сравнима с начальной по модулю 3: $D\equiv -2(\mathrm{mod}3)$ (или $D\equiv 1(\mathrm{mod}3)$).

Условие задачи требует, чтобы после каждого хода оба числа не превосходили 100: $a⩽100\text{,}$ $b⩽100\text{.}$ Тогда сумма $S=a+b⩽200\text{.}$ Из $S=12+k$ получаем $12+k⩽200\text{,}$ откуда $k⩽188\text{.}$

Рассмотрим $k=188\text{.}$ Тогда $S=12+188=200\text{.}$ Если бы оба числа были $⩽100\text{,}$ то из $S=200$ следовало бы $a=b=100\text{.}$ Но тогда разность $D=0\text{,}$ что противоречит инварианту $D\equiv 1(\mathrm{mod}3)$ (поскольку $0\equiv 0(\mathrm{mod}3)\text{,}$ а не 1). Следовательно, при $k=188$ нельзя сделать так, чтобы оба числа оставались $⩽100\text{.}$ Поэтому $k⩽187\text{.}$

Покажем, что 187 ходов можно сделать. Используем стратегию увеличения меньшего числа (как в пункте

б)). При этой стратегии можно доказать, что после $k$ ходов:

• если $k=2t$ чётное, то $a=5+t\text{,}$ $b=7+t\text{;}$
• если $k=2t+1$ нечётное, то $a=7+t\text{,}$ $b=6+t\text{.}$

Для $k=187$ (нечётное, $t=93$): $a=7+93=100\text{,}$ $b=6+93=99\text{,}$ оба числа $⩽100\text{.}$ При этой стратегии для всех меньших $k$ числа также не превышают 100 (поскольку формулы линейны и $t$ увеличивается). Следовательно, наибольшее число ходов, удовлетворяющее условию, — 187.

Ответ:

а) Нельзя.

б) 388.

в) 187.