TOAD 6 - Uniform Candy Distribution

又是一个 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\) 的平方和。 \[\begin{array}{rcl} \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 \ \end{array}\]

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