Есть числа A и B. Из них можно сделать числа A+2 и B−1 или A−1 и B+2, только если следующая пара этих чисел будет натуральной. Известно, что A=5, B=7. a) Можно ли за 50 ходов создать пару, где одно из чисел равно 100? б) За сколько ходов можно сделать пару, где сумма чисел будет равна 400? в) Какое наибольшее число ходов можно сделать, чтобы оба числа не превышали 100?
Решение
а) Заметим, что при каждом действии сумма чисел увеличивается ровно на 1. Действительно, рассмотрим каждое действие по отдельности. Если было (A,B) и стало (A+2,B−1), то сумма A+B стала равной A+2+B−1=A+B+1 Если было (A,B) и стало (A−1,B+2), то сумма A+B стала равной A−1+B+2=A+B+1 Значит, за 50 ходов сумма увеличится на 50, то есть будет равна 5+7+50=62 Так как числа всегда остаются натуральными, то при такой сумме ни одно из чисел не может равняться 100. Ответ: нет. б) Как было показано в пункте а), сумма чисел увеличивается на 1 после каждого хода. Начальная сумма чисел равна 5+7=12. Тогда для достижения искомой суммы понадобится количество ходов, равное 400−12=388 Эту сумму можно получить путём 194-кратного применения следующего алгоритма: (A,B)→(A+2,B−1)→(A+1,B+1) Ответ: 388 ходов. в) Рассмотрим разность вида «второе число — первое число». Изначально она равна B−A=7−5=2. Далее возможны два варианта. Первый вариант: (A,B)→(A+2,B−1). Тогда новая разность: (B−1)−(A+2)=B−A−3 Второй вариант: (A,B)→(A−1,B+2). Тогда новая разность: (B+2)−(A−1)=B−A+3 Числа B−A, B−A−3 и B−A+3 имеют одинаковый остаток при делении на 3. То есть разность второго и первого чисел (именно в этом порядке) всегда даёт один и тот же остаток при делении на 3. Изначально эта разность равна 2, то есть даёт остаток 2 при делении на 3. Приведем пример на 187 ходов, когда из чисел (5,7) сделаем пару (100,99) следующим образом: (5,7)187 ходов(100,99) Предположим, что ходов хотя бы 188. Тогда сумма чисел составит хотя бы 5+7+188=200 С учётом требуемого условия (получить (100,99)) это возможно, только если оба числа равны 100 и ходов было 188, но это невозможно, так как в таком случае разность чисел 100−100=0 не даёт остаток 2 при делении на 3. Получили противоречие. Следовательно, наибольшее число ходов равно 187.