Question

Изначально на доске написаны числа 3 и 6. за один ход два числа, написанные на доске, стираются, а вместо них пишутся два других, одно из которых является суммой только что стёртых чисел,а второе равно 2х+2, где х-одно из только что стёртых чисел. а) может ли за несколько ходов на доске оказаться число 44. б) может ли после 80 ходов из двух чисел, написанных на доске, оказаться числом 630. в) сделали 519 ходов. какое наименьшее значение может принимать разность большего и меньшего из полученных чисел.

Answer 1

А) Не может. Заметим, что на каждом шаге получается одно четное число и одно нечетное, причем четное число равно 2x+2, где x – одно из чисел на шаге, а нечетное равно сумме двух чисел на шаге, так как сумма четного и нечетного чисел всегда нечетна. Предположим, что число 44 получить можно, значит, оно было получено из числа 21, поскольку 21*2+2=44. В свою очередь, число 21 должно равняться сумме 2 чисел с предыдущего шага. Из начальной пары (3,6) можно получить либо пару (8,9), либо пару (9,14). Если была получена пара (8,9), то из неё может быть получена одна из пар (17,18), (17,20), из которых нельзя получить число 21. Из пары (9,14) также нельзя получить число 21, поскольку сумма 9+14 уже больше 21. Следовательно, числа 21 и 44 ни при какой последовательность ходов получены быть не могут.

б) Не может. Заметим, что на каждом шаге наименьшее число в паре увеличивается не менее чем в 2 раза. Следовательно, через 80 ходов каждое из двух чисел будет заведомо не меньше $3\cdot 2^{80}$, а это число в свою очередь значительно больше 630. 

в). 1. Покажем, что разность 0 получиться не может. Действительно, как показано выше, на каждом шаге одно из чисел обязательно будет четным, а другое нечетным. Следовательно, разность большего и меньшего чисел будет заведомо не меньше 1. Она может быть равна 1, если от пары (3,6) перейти к паре (8,9), а каждым следующим ходом получать число 2x+2 из наименьшего числа пары. Тогда сумма чисел пары будет равна 2x+1 и числа в новой паре (2x+1,2x+2) опять будут отличаться на 1.