連鎖時計パズルの可換性

705

連鎖時計パズルとは

108Hassiumさんのブログ記事で紹介されている「連鎖時計パズル」について考えてみたところ、疑問6（可換性）が解けたので、それについて解説する。元記事も非常に面白いので必読である。
元記事： https://note.com/108hassium/n/nbf8412349447

連鎖時計とは次のような装置である。

平面上のいくつかの格子点に時計が置かれている。
時計の針は1本で、上下左右の4方向を指すことができ、時計回りに動作する。
時計を叩くとその時計の針がひとつ進む。
時計 $x$ の針が進んだあと、 $x$ の針の指す方向に隣接する時計 $y$ があれば、 $y$ の針もひとつ進む。

例えば時計が以下のように $2 \times 2$ の正方形状に置かれているとしよう。
$(\begin{matrix} ↑ & \to \\ ↓ & \leftarrow \end{matrix})$
このとき、左上の時計を叩くと時計は以下のように連鎖的に動作する。
$(\begin{matrix} ↑ & \to \\ ↓ & \leftarrow \end{matrix}) \to (\begin{matrix} \to & \to \\ ↓ & \leftarrow \end{matrix}) \to (\begin{matrix} \to & ↓ \\ ↓ & \leftarrow \end{matrix}) \to (\begin{matrix} \to & ↓ \\ ↓ & ↑ \end{matrix}) \to (\begin{matrix} \to & \leftarrow \\ ↓ & ↑ \end{matrix}) \to (\begin{matrix} ↓ & \leftarrow \\ ↓ & ↑ \end{matrix}) \to (\begin{matrix} ↓ & \leftarrow \\ \leftarrow & ↑ \end{matrix})$

この記事で考えたいのは次の問題である。

（元記事の疑問6）

連鎖時計において、「時計 $x$ を叩いた後に時計 $y$ を叩く」操作と「時計 $y$ を叩いた後に時計 $x$ を叩く」操作は常に同じ結果をもたらすか？

なお、元記事の疑問2についてはPratonさんにより反例の存在が指摘されている。
https://x.com/rettouw/status/1916469288858480962

数学的定式化

証明を書きやすくするために、問題設定を数学的な言葉で書き直すとともに、状況を抽象化する。

連鎖時計においては、時計の針が何周したかという情報は時計から読み取ることができない。そこで「時計の状態は整数値で管理されており、その値を $4$ で割った余りに応じて針の向きが決まっている」と考えることにしよう。この時計の内部状態を表す整数を内部カウンターと呼ぶ。内部カウンターが $0$ のときは針は上を指し、 $5$ のときは右を指すという具合である。

連鎖時計の挙動は「時計の内部カウンターが $n$ のときに針がどの時計を指しているか」という隣接関係の情報だけから決まる。そこで次のように定義する。

抽象連鎖時計とは有限集合 $S$ と写像 $f : S \times Z \to S ⊔ {*}$ の組のことである。

通常の連鎖時計に対して、 $S$ を時計の集合とし、 $f (x, n)$ を「時計 $x$ の内部カウンターが $n$ のときに針が指す時計」（存在しないときは $*$ ）とすることで抽象連鎖時計が得られる。つまり、通常の連鎖時計は抽象連鎖時計の特別な場合とみなせる。

抽象連鎖時計 $(S, f)$ の状態とは、集合 $V := Map (S, Z)$ の元のことである。 $V$ 上の半順序 $\leq$ を
$v \leq v^{'} ⟺ \forall x \in S, v (x) \leq v^{'} (x)$
により定める。また $v \in V$ に対して
$| v | = \sum_{x \in S} v (x)$
と定める。

通常の連鎖時計の場合には、状態 $v \in V$ は「時計 $x$ の内部カウンターが $v (x)$ である状態」と解釈できる。

$(S, f)$ を抽象連鎖時計とする。状態 $v, v^{'} \in V$ および $z \in S ⊔ {*}$ に対し、三項関係 $v \overset{z}{\to} v^{'}$ を以下のように帰納的に定義する。

$| v^{'} - v | < 0$ のときは $v ⧸ \overset{z}{\to} v^{'}$ .
$| v^{'} - v | = 0$ のときは $v \overset{z}{\to} v^{'} ⟺ v = v^{'}, z = * .$
$| v^{'} - v | > 0$ のときは $v \overset{z}{\to} v^{'} ⟺ v + δ_{x} \overset{f (z, v (z) + 1)}{\to} v^{'}$ .

ただし $δ_{x}$ は $δ_{x} (y) = δ_{x, y}$ で定まる $V$ の元である。

通常の連鎖時計の場合には、 $v \overset{z}{\to} v^{'}$ は「状態 $v$ において時計 $z$ を叩くことで状態 $v^{'}$ に到達する」ということを表している。

操作の復元

以下、 $(S, f)$ を抽象連鎖時計とする。 $v \overset{z}{\to} v^{'}$ のとき、 $z$ を $v$ と $v^{'}$ のみから求めることはできるだろうか？この疑問に答えるために以下のような関数を定義しよう。

状態 $v, v^{'} \in V$ が $v \leq v^{'}$ を満たすとき、 $g_{v, v^{'}} \in V$ を
$g_{v, v^{'}} (x) = \sum_{y \in S} # {v (y) < n \leq v^{'} (y) ∣ f (y, n) = x}$
により定める。

通常の連鎖時計の場合には、 $g_{v, v^{'}} (x)$ は「状態が $v$ から $v^{'}$ に変化する過程で時計 $x$ が隣接する時計から指された回数」を表している。定義から明らかに以下が成り立つ。

状態 $v, v^{'}, v^{″} \in V$ が $v \leq v^{'} \leq v^{″}$ を満たすとき
$g_{v, v^{'}} + g_{v^{'}, v^{″}} = g_{v, v^{″}}$
が成り立つ。

この関数 $g_{v, v^{'}}$ を使うと、 $v \overset{z}{\to} v^{'}$ のときに $v, v^{'}$ から $z$ を求めることができる。

$v \overset{z}{\to} v^{'}$ ならば
$v^{'} \geq v, v^{'} - v = g_{v, v^{'}} + δ_{z}$
が成り立つ。特に $z$ は $v, v^{'}$ から一意的に定まる。

$| v^{'} - v |$ に関する帰納法で示す。 $v \overset{x}{\to} v^{'}$ なので $| v^{'} - v | \geq 0$ である。 $| v^{'} - v | = 0$ ならば $v = v^{'}, z = *$ なので主張は明らかに成り立つ。 $| v^{'} - v | > 0$ とすると、定義から
$v + δ_{z} \overset{f (z, v (z) + 1)}{\to} v^{'}$
である。帰納法の仮定より
$v^{'} \geq v + δ_{z}, v^{'} - v - δ_{z} = g_{v + δ_{z}, v^{'}} + δ_{f (z, v (z) + 1)}$
である。ここで $g_{v, v^{'}}$ の定義より
$g_{v + δ_{z}, v^{'}} = g_{v, v^{'}} - δ_{f (z, v (z) + 1)}$
が成り立つので、上の式に代入することで所望の式が得られる。

操作後の状態の特徴づけ

引き続き $(S, f)$ を抽象連鎖時計とする。以下の定理が本記事における鍵である。

$v \overset{z}{\to} v^{'}$ とする。このとき $v^{'}$ は
$\begin{matrix} (1) & w \geq v, w - v \geq g_{v, w} + δ_{z} \end{matrix}$
が成り立つような $w \in V$ 全体における最小元である。すなわち、式 $(1)$ を満たす任意の $w \in V$ に対して $v^{'} \leq w$ が成り立つ。

$| v^{'} - v |$ に関する帰納法で示す。 $v \overset{x}{\to} v^{'}$ なので $| v^{'} - v | \geq 0$ である。 $| v^{'} - v | = 0$ ならば $v = v^{'}$ なので主張は明らかに成り立つ。 $| v^{'} - v | > 0$ とすると、定義から
$v + δ_{z} \overset{f (z, v (z) + 1)}{\to} v^{'}$
である。式 $(1)$ を満たす $w \in V$ を任意に取ると
$w (z) - v (z) \geq g_{v, w} (z) + 1 \geq 1$
なので $w \geq v + δ_{z}$ が成り立つ。また $g_{v, v^{'}}$ の定義より
$g_{v + δ_{z}, w} = g_{v, w} - δ_{f (z, v (z) + 1)}$
が成り立つので、式 $(1)$ に代入することで
$w - v - δ_{z} \geq g_{v + δ_{z}, w} + δ_{f (z, v (z) + 1)}$
が得られる。よって帰納法の仮定を $v + δ_{z} \overset{f (z, v (z) + 1)}{\to} v^{'}$ に適用することで $v^{'} \leq w$ が得られる。

定理3は複数回の操作に対しても一般化できる。

抽象連鎖時計 $(S, f)$ において
$v \overset{z_{1}}{\to} v_{1} \overset{z_{2}}{\to} v_{2} \overset{z_{3}}{\to} \dots \overset{z_{n}}{\to} v_{n}$ のとき、 $v_{n}$ は
$\begin{matrix} (2) & w \geq v, w - v \geq g_{v, w} + \sum_{i = 1}^{n} δ_{z_{i}} \end{matrix}$
が成り立つような $w \in V$ 全体における最小元である。

$n$ に関する帰納法で示す。 $n = 1$ のときは定理3そのものである。 $n \geq 2$ とし、式 $(2)$ を満たす $w \in V$ を任意に取る。すると特に
$w \geq v, w - v \geq g_{v, w} + δ_{z_{1}}$
が成り立つので、定理3より $v_{1} \leq w$ となる。さらに $v_{1} - v = g_{v, v_{1}} + δ_{z_{1}}$ より
$\begin{aligned} w - v_{1} & = w - v - g_{v, v_{1}} - δ_{z_{1}} \\ \geq g_{v, w} + \sum_{i = 1}^{n} δ_{z_{i}} - g_{v, v_{1}} - δ_{z_{1}} \\ = g_{v_{1}, w} + \sum_{i = 2}^{n} δ_{z_{i}} \end{aligned}$
が成り立つので、帰納法の仮定より $v_{n} \leq w$ となる。