Инвариант: множество остатков чисел по модулю $2^k$ для каждого $k$. Заметим, что полусумма двух чисел целая тогда и только тогда, когда они одинаковой чётности. При замене $(a, b) \to \frac{a+b}{2}$ уменьшается количество чисел, делящихся на $2^k$, строго закономерным образом. Рассмотрим $2-$адические значения чисел: $v_2(a)$ и $v_2(b)$. Если $v_2(a) = v_2(b) = k$, то $v_2(\frac{a+b}{2}) \geq k$. Процесс «слияния» чисел с одинаковым $2-$адическим значением однозначно определяется мультимножеством этих значений. Поскольку на каждом шаге мы объединяем пару с минимальным возможным $2-$адическим значением, конечный набор определяется однозначно и не зависит от порядка ходов.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!