43-я Балканская математическая олимпиада. Греция, Салоники, 2026 год

$n \geq 2$ — бүтін сан болсын. Бастапқыда тақтаға $n$ рет 1 саны жазылған. Операция деп тақтадағы екі санды $a$ және $b$ (екеуі бірдей нөл емес) таңдап, оларды келесі сандармен алмастыруды айтамыз: $$ \frac{(a-b)^2}{a+b} \text{ және } \frac{4ab}{a+b}. $$ Қандай $n$ бүтін сандары үшін шекті саны операциялардан кейін тақтада $n$ саны пайда болуы мүмкін екенін анықтаңыз.

Комментарий/решение

Ответ: $n$ - степень двойки.

Необходимость. Пусть $n$ имеет нечетный простой делитель $p$. Для определённости будем считать $v_p(0) = +\infty$. В любой момент на доске конечное число ненулевых чисел. Рассмотрим минимальную $p$-адическую оценку среди них:

$m = \min \{v_p(x)\}$, где $x$ - ненулевое число на доске. Изначально все числа единицы, потому $m = 0$. Покажем, что $m$ не может увеличиваться. Возьмём два числа $a,b$, причем $v_p(a)=i$, $v_p(b)=j$, обозначим $S = a+b$, $x = (a-b)^2/S$, $y = 4ab/S$.

$i \neq j$ (БОО $i < j$), то $v_p(S)=i$, $v_p(a-b)=i$, $v_p(y)=i+j-i=j$, $v_p(x)=2i-i=i$. Набор $\{i,j\}$ не изменился.

$i=j=k$. Пускай $a=up^k$, $b=wp^k$, причем $u,w$ не кратны $p$. Тогда $a+b=(u+w)p^k$, $a-b=(u-w)p^k$. Обозначим $t=v_p(u+w) \ge 0$, $s=v_p(u-w) \ge 0$. Для нечетного $p$ числа $u$ и $w$ не могут одновременно быть сравнимы и с $-1$ и с $1$ по модулю $p$. Рассмотрим 3 случая:

$u \not\equiv \pm w \pmod p$, $t=s=0$. Тогда $v_p(x)=v_p(y)=k$. Набор $\{k,k\}$ не изменился.

$u \equiv w \pmod p$, $s\ge 1$, $t=0$. Тогда $v_p(y)=k$, $v_p(x)=k+2s>k$. Теперь набор $\{k,k+2s>k\}$, минимум $k$ тот же.

$u \equiv -w \pmod p$, $t\ge 1$, $s=0$. Тогда $v_p(x)=v_p(y)=k-t \le k-1$. Набор $\{k-t,k-t\}$ имеет минимум $k-t<k$.

Таким образом, при любой операции минимальная оценка двух чисел не возрастает, т.е. $m \le 0$. Но если бы мы добились требуемого, были бы числа $n,0,0,\dots$, $v_p(0)>0$, $v_p(n) \ge 1$ (т.к. $p\mid n$) - противоречие.

Достаточность. Пройдёмся индукцией по $m$, что $n = 2^m$ удовлетворяет, база $m = 1$ очевидна. Шаг: Пусть из $2^m$ единиц можно получить $2^m$ и $2^m-1$ нулей. Возьмём $2^{m+1}$ единиц. Разобьем их на пары и в каждой паре заменим $(1,1)$ на $(0,2)$. Получим $2^m$ двоек и $2^m$ нулей. Если вместо $(a,b)$ мы имеем $(2a,2b)$, то результат будет $(2x,2y)$, т.к. операция однородна. Потому, повторяя на двойках ту же последовательность действий, что в предположении для единиц, мы получим одно число $2 \times 2^m = 2^{m+1}$ и остальные нули (подчеркнем здесь, что $(a,0) \to (0,a)$).