簡単な不変量の問題
競技数学 - 黒板の数を操作する問題
なかなか教育的な問題ではないでしょうか。
問題
$n \ge 2$ 個の整数 $a_1,\dots,a_n$
が黒板に書かれている。 黒板上の任意の2数
$x,y$ に対する操作を、$x,y$ を黒板から削除し
\( \left\lfloor\frac{x+y}{2}\right\rfloor,
\left\lceil\frac{x+y}{2}\right\rceil \)
を新たに書き込むことと定義する。
有限回の操作の後に、任意の2数に対して操作を行っても黒板に書かれている数が変化しないような状態に到達することを示せ。
さらに、到達する最終状態において黒板に書かれている数の種類は2種類であり、各数の個数は
初めに黒板に書かれている数によって一意に定まることを示せ。
解説
以下では、操作の不変量と単調減少量を厳密に定式化し、 それらを用いて主張を証明する。
(i) 総和 $\displaystyle S=\sum_{i=1}^n a_i$
は操作によって不変である。
(ii) 平方和 \(\displaystyle P=\sum_{i=1}^n
a_i^2 \) は操作によって増加せず、 もし選んだ
2 数 $x,y$ が $|x-y|\ge2$ を満たすなら、
その操作により $P$ は少なくとも $2$
減少する。
(i)は直ちに従う。実際、任意の 2 数 $x,y$
に対し \[ \left\lfloor\frac{x+y}{2}\right\rfloor
+ \left\lceil\frac{x+y}{2}\right\rceil = x+y \]
が成り立つ。よって操作前後で総和は変化しない。
(ii)を証明する。$s=x+y$ とおく。 $s$
の偶奇により \[
\left\lfloor\frac{s}{2}\right\rfloor
=\frac{s-r}{2},\qquad
\left\lceil\frac{s}{2}\right\rceil
=\frac{s+r}{2} \] と書ける。ただし $r\in\{0,1\}$
であり、 $r\equiv s\pmod2$ である。 よって \[
\left(\frac{s-r}{2}\right)^2 +
\left(\frac{s+r}{2}\right)^2 =
\frac{s^2+r^2}{2}. \] 一方、 \[ x^2+y^2 =
\frac{(x+y)^2+(x-y)^2}{2} =
\frac{s^2+(x-y)^2}{2}. \]
したがって操作による二乗和の減少量 $\Delta$ は
\[ \Delta = (x^2+y^2) - \left(
\left\lfloor\frac{s}{2}\right\rfloor^2 +
\left\lceil\frac{s}{2}\right\rceil^2 \right) =
\frac{(x-y)^2-r^2}{2}. \] $r\equiv s\equiv
x-y\pmod2$ であるから、 $(x-y)^2-r^2$
は偶数であり、また $\Delta$ は整数である。
さらに $|x-y|\ge2$ のとき $(x-y)^2\ge4$ かつ
$r^2\le1$ であるから \[ \Delta \ge \frac{4-1}{2}
= \frac32. \] $\Delta$ は整数であるから
$\Delta\ge2$。 よって命題は示された。 $\square$
以上を用いて主張を証明する。
まず命題１より、 差が $2$ 以上の 2
数を選んで操作を行うたびに、 二乗和 $P$
は少なくとも $2$ ずつ減少する。 $P$
は非負整数であるから、
このような操作は有限回しか行えない。
したがって有限回の操作の後、 任意の 2 数
$a_i,a_j$ は \[ |a_i-a_j|\le1 \]
を満たす状態に到達する。
このとき黒板上に現れる整数は高々 2
種類であり、 それらはある整数 $t$ と $t+1$
である。 実際、差が高々 $1$ である整数の集合は
必ずこの形に限られる。
$t+1$ が $k$ 個、 $t$ が $n-k$
個存在するとすると、 総和不変性より \[ S =
(n-k)t + k(t+1) = nt+k \] が成り立つ。 よって
$k\equiv S\pmod n$ かつ $0\le k < n$ であり、
$k$ は一意に定まる。
したがって最終状態における各整数の個数は
初期総和 $S$ のみによって一意に定まる。
以上により、有限回の操作の後に
主張された形の状態に到達し、
その分布は総和によって一意に定まることが示された。
$\square$