又是一个 Matrix67 大大翻译过的题。

Problem

$n$ 个人围成一圈，第 $i$ 个人手中有一个数 $a_i$ 。现在重复执行以下两步：

1. 如果 $a_i$ 是奇数，则把 $a_i$ 加 1
2. $a'_i \leftarrow \frac{1}{2}(a_i + a_{i+1})$

证明：有限步后，所有的数一定相同。

Solution

考虑 $a$ 里面的最大值。考虑最小的一个 $2^t$ 大于最大值 $a_x$ 。显然 $a_x$ 怎么增加，最终是不可能超过 $2^t$ 的。

再考虑 $a$ 的和。由于最大值有限，所以和一定有限，易知有限步之后， $a$ 的和一定不变。

考虑 $a$ 和不变后的状态。则任意时刻所有的 $a_i$ 一定为偶数。我们考虑 $a$ 的平方和。

$$\sum a^2_i - \sum a'^2_i = \sum a^2_i - \sum ( \frac{a_i + a_{i+1}}{2})^2 = \sum a^2_i - \sum (\frac{1}{2} a^2_i + a_i a_{i+1}) = \frac{1}{2} \sum (a_i - a_{i+1})^2$$

可以看到，如果 $a$ 不是全等的，则 $a$ 的平方和一定会减小。由于每次减小的量是至少是 $\frac{1}{2}$ ，所以经过有限次变换之后， $a$ 一定全部相同。