В игре число a=4 и число b=5, за ход можно сделать (a−1;b+2) или (a+2;b−1). Новые числа a и b всегда положительные.
а) Можно ли получить число 200 за 100 ходов?
б) Сколько нужно сделать ходов, чтобы получить сумму, равную 300?
в) Сколько нужно сделать ходов, чтобы получить максимальную сумму, при этом ни одно число не превышает 200.
Решение
\item Заметим, что при каждом ходе сумма чисел увеличивается на 1.
Действительно, если из пары (a;b) перейти к паре (a−1;b+2), то новая сумма равна(a−1)+(b+2)=a+b+1.Если из пары (a;b) перейти к паре (a+2;b−1), то новая сумма равна(a+2)+(b−1)=a+b+1.Изначальноa+b=4+5=9.Значит, через 100 ходов сумма чисел будет равна9+100=109.Так как сумма двух положительных чисел равна 109, ни одно из этих чисел не может быть равно 200.
Следовательно, получить число 200 за 100 ходов нельзя.
\item Так как при каждом ходе сумма увеличивается на 1, то для получения суммы 300 нужно сделать300−9=291ход.
Осталось показать, что это действительно возможно.
Заметим, что за два хода можно перейти(a;b)⟶(a+2;b−1)⟶(a+1;b+1).То есть за два хода оба числа увеличиваются на 1.
Сделаем так 145 раз. Тогда будет сделано 290 ходов, и из пары (4;5) получится пара(4+145;5+145)=(149;150).После этого сделаем еще один ход:(149;150)⟶(151;149).Сумма полученной пары равна151+149=300.Значит, сумму 300 можно получить за 291 ход.
\item Так как ни одно число не должно превышать 200, то сумма не может быть больше200+200=400.Покажем, что сумму 400 получить нельзя.
Рассмотрим разность b−a. Изначальноb−a=5−4=1.Если перейти от пары (a;b) к паре (a−1;b+2), то новая разность равна(b+2)−(a−1)=b−a+3.Если перейти от пары (a;b) к паре (a+2;b−1), то новая разность равна(b−1)−(a+2)=b−a−3.Значит, при каждом ходе разность b−a изменяется на число, кратное 3.
Так как в начале b−a=1, то после любого количества ходов разность b−a не может стать равной 0.
Если бы сумма была равна 400, то, так как каждое число не превышает 200, пришлось бы иметьa=200,b=200.Но тогдаb−a=0,что невозможно.
Значит, сумма 400 недостижима, поэтому максимальная возможная сумма не больше 399.
Покажем, что сумму 399 получить можно.
Из пункта б) уже знаем, что за два хода можно перейти(a;b)⟶(a+2;b−1)⟶(a+1;b+1).Сделаем так 194 раза. Тогда будет сделано 388 ходов, и получим пару(4+194;5+194)=(198;199).Теперь сделаем еще два хода:(198;199)⟶(200;198)⟶(199;200).На каждом шаге оба числа положительные и не превышают 200.
Сумма последней пары равна199+200=399.Значит, максимальная сумма равна 399.
Так как за каждый ход сумма увеличивается на 1, а начальная сумма равна 9, чтобы получить сумму 399, нужно сделать399−9=390ходов.
