Задание 19 ЕГЭ, математика (профиль): Числа и их свойства

а) Пример цепочки. Берём пары чисел и применяем правило $(a,b)\to(a+b,\,2a-1)$ или $(a,b)\to(a+b,\,2b-1)$. $(2,3)\to$ выбираем $2b-1$: получаем $(5,5)$. $(5,5)\to$ выбираем $2a-1$: получаем $(10,9)$. $(10,9)\to$ выбираем $2a-1$: получаем $(19,19)$. Число 19 появилось на доске.

б) Почему 200 нельзя получить за 100 ходов. Обозначим через $m_k$ наименьшее из двух чисел после $k$-го хода. После первого хода из $(2,3)$ минимальное возможное число равно $3$ (варианты $(5,3)$ или $(5,5)$). Далее, если перед ходом минимум пары равен $m\ge 3$, то оба новых числа не меньше: сумма $a+b\ge 2m\ge m+2$, а число вида $2x-1$ (где $x\ge m$) даёт $2x-1\ge 2m-1\ge m+2$ при $m\ge 3$. Значит, каждый следующий ход увеличивает минимум хотя бы на $2$. После $100$ ходов минимум не меньше $3+2\cdot 99=201>200$, значит число $200$ появиться не может.

в) Оценка и пример для 1007 ходов. Исходные числа $2$ и $3$ отличаются на $1$, то есть имеют вид $a,\;a+1$. Применяя правило, получаем либо равные числа $2a-1,\;2a+1$... на самом деле $2a\!-\!1$ и $2(a+1)\!-\!1=2a+1$ — те же самые числа отличаются уже на $2$, либо (при другом выборе) равные числа, что запрещено условием. Значит, если равенство исключено, разность соседних чисел на доске всегда чётна и минимально возможное её значение — $2$. При этом чётность самих чисел меняется предсказуемо: после нечётного хода получаются два нечётных числа, после чётного — чётное и нечётное. Ход №1007 — нечётный, поэтому после него оба числа нечётные, а различные нечётные числа не могут отличаться меньше, чем на $2$. Показываем, что разность $2$ достижима: цепочка $(2,3)\to(3,5)\to(8,9)\to(15,17)\to(32,33)\to\dots$, по общей схеме $(a,a+1)\to(2a-1,2a+1)\to(4a,4a+1)\to(8a-1,8a+1)\to\dots$ — на каждом шаге разность чисел либо $1$, либо $2$, и за 1007 ходов можно устроить так, что в конце разность равна именно $2$. Следовательно, наименьшее возможное значение разности — $2$.