Задача 67406
|
|
 |
Условие
Назовём двуклетчатую карточку $2\times 1$ правильной, если в ней записаны два натуральных числа, причём число в верхней клетке меньше числа в нижней клетке. За ход разрешается изменить оба числа на карточке: либо прибавить к каждому одно и то же целое число (возможно, отрицательное), либо умножить каждое на одно и то же натуральное число, либо разделить каждое на одно и то же натуральное число; при этом карточка должна остаться правильной. За какое наименьшее количество таких ходов из любой правильной карточки можно получить любую другую правильную карточку?Решение
Будем изображать карточку в виде пары $(a, b)$, где $a < b$. Пусть надо из $(a, b)$ получить $(c, d)$. Умножим первую карточку на разность $d – c$ чисел на второй карточке, получим карточку $(a(d – c), b(d – c))$. Вторым ходом получим из неё карточку $(c(b – a), d(b – a))$. Это можно сделать с помощью сложения, так как разность между нижним и верхним числами на каждой из этих карточек равна $(b – a)(d – c)$. Третьим ходом делим на разность $b – a$.Докажем, что из карточки $(1, 3)$ нельзя получить карточку $(1, 4)$ меньше, чем за три хода. Для нашей карточки первый ход – прибавление натурального числа или умножение (так как на ней есть $1$).
В первом случае разность чисел на карточке останется равной $2$, и за одно деление или умножение получить разность $3$ нельзя (разность умножится или разделится на целое число); сложение разность вообще не изменит.
Во втором случае, чтобы изменить отношение чисел на карточке с $3$ на $4$, придётся вторым ходом использовать вычитание, тогда разность уже должна была равняться $3$, но она кратна $2$.
