嘘つきクイズを線型代数で解く

導入

こんにちは. 今回は, 次のような簡単な嘘つきクイズを面白い方法で解いてみましょう.

${}$

変数をおく

A~Eが嘘つきか正直者かを, 変数$a\sim e$で表すことにします. 嘘つきの場合は$1$, 正直者の場合は$0$としておきましょう.

以下, $\F_2=\mathbb{Z}/2\mathbb{Z}$（2で割った余りの世界）で考えます.

${}$

Aの主張「Cは正直者だ」は, そのまま式で表すと「$c=0$」となりますが, これでは正しくありません. 実際にはAが嘘つきかどうかで変わってくるからですね.

ではどう変わるかというと, Aが嘘つきならば右辺の0or1が反転することになります. つまり, 左辺に$a$を足して「$c+a=0$」とすれば, Aの嘘も加味した正しい式になるのです！

（実際, $a=0$のときは「$c=0$」となりCは正直者という主張で, $a=1$のときは「$c=1$」となりCは嘘つきだったことになります.）

${}$

この調子で数式に書き換えていけば,

A「Cは正直者だ」　　　 →　　$c+a=0$
B「C, Eは嘘つきだ」 　 →　　$c+b=1,\ e+b=1$
C「A, Dは正直者だ」 　 →　　$a+c=0,\ d+c=0$
D「Aは正直者だ」　　　 →　　$a+d=0$
E「Bは嘘つきだ」　　　 →　　$b+e=1$

となり, いくつか被りがありますから整理すると, 問題は次のように書き換えられます.

${}$

線型代数を使う

線型代数の言葉を使えば, 先の問題は次のように書けます.（有限体上の線型代数は知らないよという方でも, 以下は普通の行列の話と思って読んでもらって大丈夫です.）

$$ \begin{pmatrix} 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 \end{pmatrix} \begin{pmatrix} a\\b\\c\\d\\e \end{pmatrix} = \begin{pmatrix} 0\\0\\1\\1\\0 \end{pmatrix} $$

左辺の$5\times5$行列を$A$とおいておきます. このような方程式を調べるには$A$の$\rank$を見れば良いですね.

${}$

あとは計算するだけです. 1行目と2行目を5行目に足し, 1行目を3行目に足せば
$$ A\sim \begin{pmatrix} 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$
となり, 適当に並べ替えれば$\rank A=4$であることが分かります. 従って特に, 上の方程式は一意には解けません.

${}$

上の方程式の右辺が$\mathrm{Im}\,A$に入っていれば解が求められますが, 実際$b$のみ$1$とすると方程式を満たします. 従って解は

$$ \begin{pmatrix} 0\\1\\0\\0\\0 \end{pmatrix}+\mathrm{Ker}\,A$$

の元となります. $\rank A=4$より$\dim\mathrm{Ker}\,A=1$ですから, （$\F_2$上$1$次元なので）解は$2$つであるとわかります.

$\mathrm{Ker}\,A$を求めれば解を具体的に求めることもできます.

${}$

おわりに

発言に「少なくとも」といった主張が出てくると積を使わないといけないので線型代数では解けなくなってしまいます. またよくある「嘘つきは何人いる」といった条件もうまく表現できません. なのでこれは観賞用解法といったところですね.

ここまで読んでくださった方, ありがとうございました.

${}$