На доске написаны натуральные числа $1, 2, 3, …n$, где $n \geq 3$. За один ход разрешается заменить любые два числа $x$ и $y$ на числа $x + y$ и $|x – y|$. После нескольких ходов оказалось, что все написанные на доске числа равны $k$. Каковы возможные значения числа $k$?
Может ли число $k$ иметь нечетные делители?
Ответ: $k = 2^m$, где $m$ – натуральное число, такое, что $2^m \geq n$ После каждого хода на доске будут целые неотрицательные числа. Если сумма и разность двух таких чисел делится на нечетное число $d$, то и сами эти числа делятся на $d$. Поэтому, если бы $k$ делилось на нечетное $d>1$, то и все первоначальные числа должны делиться на $d$, что не соответствует условию. Поэтому у числа $k$ нет нечетных делителей, то есть $k=2^m$. Так как после каждого хода максимальное из чисел не уменьшается, то $k \geq n$. Основные приемы конструирования набора из одинаковых чисел: из пары $ (2^a, 2^a)$ получается пара $(0, 2^{a+1}) $, из пары $(0, 2^a) $ получается пара $ (2^a, 2^a) $. На примерах (в скобках заменяемые числа) показано как из набора $1234$ получить набор $4444$, из набора $12345$ – набор $88888$, из набора $123456$ – набор $888888$. $1234 ~ (13)24 ~ 2424 ~ (22)44 ~ (04)44 ~ 4444$ $12345 ~ (14)(35)2 ~ (35)282 ~ 28282 ~ (22)288 ~ 04288 ~ (24)088 ~ (26)088 ~ 48088 ~ (04)888 ~ (44)888 ~ (08)888 ~ 88888$ $123456 ~ (14)(35)(26) ~ (35)2848 ~ 282848 ~ (22)4888 ~ 044888 ~ (44)0888 ~ (08)0888 ~ 880888 ~ (08)8888 ~ 888888$
