『「異様に難しいドラクエの謎解き」をモデル検査器で解く』代わりに数学で解く

前置き

タイトルは本歌取りもいい加減にしろ, という長さですが. こんなつぶやきをしたので, 予告どおり記事を書きます.

酒井さんの続きの記事 → http://msakai.jp/d/?date=20130402#p01

解説

まず方針としては酒井さんと同じく連立方程式を解きます. 酒井さんはモデル検査を用いて解いていますが, 私は数学で解きます. 一応, 数学を学んできた身としては, 数学で解けるものは数学で解きたいものです. (酒井さんも同じようなお考えなのかもしれません) 数学を使って厳密に解いてしまえば, この解が最適解かどうか考えるのも楽になります. 手法による違いを楽しんでいただけたら, と思います.

まず最初に立式する連立方程式は同じです.

$$ \begin{aligned} x_1 + x_2 + x_3 + a_1 &\equiv b_1\ (\bmod 4) \\ x_2 + x_3 + x_4 + a_2 &\equiv b_2\ (\bmod 4) \\ x_1 + x_3 + x_4 + a_3 &\equiv b_3\ (\bmod 4) \\ x_1 + x_2 + x_4 + a_4 &\equiv b_4\ (\bmod 4) \end{aligned} $$

4 次元の縦ベクトル \(\mathbf{a}\) は 4 つの銅像の初期状態, \(\mathbf{b}\) は終了状態を表します. 各要素は内側を向いている状態を 0 として, 右回りに 90 度回るごとに 1 増えるとします.

与えられた \(\mathbf{a}\) に対し \(\mathbf{b} \equiv 0\) の条件で \(\mathbf{x}\) について解くのですが, ここでおもむろに行列を持ち出します.

$$ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} + \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned} $$

こうして

$$ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \equiv \begin{pmatrix} - a_1 \\ - a_2 \\ - a_3 \\ - a_4 \end{pmatrix} \end{aligned} $$

こうして

$$ \begin{aligned} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \equiv \begin{pmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 2 \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix} \end{aligned} $$

はい, 解けた. \(\bmod 4\) ではこれが唯一の解です. その代表元を取るときに \([0, 4)\) の範囲で取れば, それが即ち最適解です. 行列で書いていますが, やってることは連立方程式を解いてるだけですね.

試しに

$$ \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \\ 0 \\ 0 \end{pmatrix} $$

で解いてみると

$$ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 2 \\ 1 \end{pmatrix} $$

と同じ答えが得られます.

ここで終わりにすると解法を覚えるだけの単なる算数になってしまいます. ここから先に考えるのは, 解の存在と一意性. そして (もしあれば) その条件です. 平たく言うと「似たような問題でもいつでも解けるのか? 例えばボタンを押したときに別の箇所が回るようになっていても解けるのか?」ということです.

上の式でも分かるように

$$ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} \end{aligned} $$

という行列がキモなのです. この行列の性質について調べると, 解が存在する条件もばっちり分かります.

そこらへんを書いてると長くなるので割愛したいのと, 最近この内容の文章書いたので, そちらを見て欲しいなぁ, ということで, その文章が出るのをお待ちあれ :) そこでは, もうちょっと噛み砕いた説明をしているので期待していてください.

質問も受け付けますので, お気軽にコメントを残していってくださいな.

合わせて読みたい

Comments

blog comments powered by Disqus

Licenses