Из пары натуральных чисел (a; b) за один ход можно получить пару (a + 2; b - 1) или (a - 1; b + 2) при условии, что оба числа в новой паре положительны. Сначала есть пара (5; 7) . а) Можно ли за 50 таких ходов получить пару, в которой одно из чисел равно 100? б) За какое число ходов получится пара, сумма чисел в которой равна 400? в) Какое наибольшее число ходов можно сделать так, чтобы после каждого хода оба числа в паре не превосходили 100?

а) Заметим, что при каждом ходе сумма чисел увеличивается на 1: при ходе (a+2; b-1) сумма становится (a+2)+(b-1)=a+b+1 , при ходе (a-1; b+2) сумма становится (a-1)+(b+2)=a+b+1 . Начальная сумма 5+7=12 . После 50 ходов сумма станет 12+50=62 . Если одно из чисел равно 100, то второе равно 62-100=-38 , что не является натуральным (положительным) числом. Значит, получить такую пару за 50 ходов нельзя. б) Пусть сделано k ходов. Тогда сумма чисел станет 12+k . Чтобы сумма стала 400, нужно 12+k=400 , откуда k=388 . Покажем, что 388 ходов можно сделать, сохраняя положительность чисел на каждом шаге. Используем стратегию: на каждом шаге увеличиваем меньшее из чисел (при равенстве увеличиваем любо е). Докажем по индукции, что при такой стратегии после k ходов оба числа положительны и сумма равна 12+k . Для k=0 это верно: (5; 7) . Шаг индукции: пусть после k ходов числа a>0 и b>0 , сумма a+b=12+k . Если a b , делаем ход (a+2; b-1) . Тогда новые числа: a'=a+2>0 , b'=b-1 . Поскольку a+b=12+k , то b a >0 , и если b=1 , то a=1 (так как a b ), но тогда сумма a+b=2 , что при k таком, что 12+k=2 , т.е. k=-10 , невозможно. В общем случае, поскольку сумма растёт, b остаётся положительным. Аналогично для случая b < a . Таким образом, стратегия сохраняет положительность. Для k=388 сумма станет 400, и числа положительны. Меньшим числом ходов сумму 400 получить нельзя, так как сумма увеличивается только на 1 за ход. Следовательно, минимальное число ходов — 388. в) Введём инварианты. Пусть после k ходов числа равны a и b . Сумма S = a+b = 12+k (как в пунктах а и б). Разность D = a-b . Начальная разность D_0 = 5-7 = -2 . Каждый ход изменяет разность: при ходе (a+2; b-1) разность становится (a+2)-(b-1)=a-b+3 , т.е. увеличивается на 3; при ходе (a-1; b+2) разность становится (a-1)-(b+2)=a-b-3 , т.е. уменьшается на 3. Следовательно, разность всегда сравнима с начальной по модулю 3: D=== -2+- od3 (или D=== 1+- od3 ). Условие задачи требует, чтобы после каждого хода оба числа не превосходили 100: a 100 , b 100 . Тогда сумма S = a+b 200 . Из S=12+k получаем 12+k 200 , откуда k 188 . Рассмотрим k=188 . Тогда S=12+188=200 . Если бы оба числа были 100 , то из S=200 следовало бы a=b=100 . Но тогда разность D=0 , что противоречит инварианту D=== 1+- od3 (поскольку 0=== 0+- od3 , а не 1). Следовательно, при k=188 нельзя сделать так, чтобы оба числа оставались 100 . Поэтому k 187 . Покажем, что 187 ходов можно сделать. Используем стратегию увеличения меньшего числа (как в пункте б)). При этой стратегии можно доказать, что после k ходов: - если k=2t чётное, то a=5+t , b=7+t ; - если k=2t+1 нечётное, то a=7+t , b=6+t . Для k=187 (нечётное, t=93 ): a=7+93=100 , b=6+93=99 , оба числа 100 . При этой стратегии для всех меньших k числа также не превышают 100 (поскольку формулы линейны и t увеличивается). Следовательно, наибольшее число ходов, удовлетворяющее условию, — 187. Ответ: а) Нельзя. б) 388. в) 187.

а) нет б) 388 в) 187