室村日記

プログラミング初心者のメモ書きです

ウソつき問題とGW法

たまに見るウソつき問題にGW法という名前の万能の解法があることを知ったので,納得できるまで考えてみました.

はじめに

ウソつき問題とは以下のようなタイプの問題です.
誰しも小学生の頃にクイズ本やテレビのクイズ番組などで見たことがあると思います.

A~Dの4人が以下のようにそれぞれ証言している.
ただし,各人は必ずしも本当のことを言っているとは限らない.
A「Dはウソつきだ」
B「Cはウソつきだ」
C「AかDのどちらかはウソつきだ」
D「AかCのどちらかはウソつきだ」

このとき,以下の選択肢の中で,確実に正しいものはどれか.
1 Aはウソつきでない
2 Bはウソつきでない
3 Cはウソつきだ
4 Dはウソつきでない
5 ウソつきは2人いる

GW法の概要

正式名称はGrands Wagons法というらしいです.
さて,この作戦はたったの2ステップで表せます.
1.特定の発言によって登場人物をウソつき/正直者にグループ分けする
2.その他の発言によって正解を見つける

GW法

上の例であげた問題を考えてみます.

0.前提
まず,4人の人間がいます.
f:id:muromura:20170714143025p:plain
誰かはわかりませんが,ウソつきがいるようです.
f:id:muromura:20170714143040p:plain
ここでは正直者を白い人間,ウソつきを黒い人間で表してみます.
(あくまで例,上の問題でBとDがウソつきだというわけではないので注意)


1.グループ分け
あるタイプの証言に注目し,ルールに沿って登場人物をグループ分けします.
注目する証言のタイプは,『〜は正直者/ウソつきだ』のように特定の人物がウソつきかどうか直接的に言及しているものです.
そのとき,以下のルールに沿ってグループ分けすることができます.

・A「Bはウソつき」 なら AとBは違うグループ
・A「Bは正直」 なら AとBは同じグループ

Aがウソつきかどうかも分からないのに,本当にグループ分け出来ているの?と思ったので詳しく見てみます.

Aが「Bはウソつき」と言っている
f:id:muromura:20170714142334p:plain
f:id:muromura:20170714142755p:plain

Aが「Bは正直者」と言っている
f:id:muromura:20170714142827p:plain
f:id:muromura:20170714143202p:plain

どの場合も,AとBが同じグループに属するかどうかについて,正しく判断できていることがわかりました.

上の問題では,他者に直接言及しているのはAとBです.
ルールを適用すると,AとDは違うグループである,BとCは違うグループである,の2つがわかります.
ここでAとBがそれぞれウソつきかどうかを考えると,以下の4パターンのグループ分けが考えられます.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143612p:plain
f:id:muromura:20170714143603p:plain
f:id:muromura:20170714143607p:plain




2.正解を見つける
つぎに,残るCとDの発言に注目して正解を見つけたいと思います.

Cの発言に注目すると,「AかDのどちらかはウソつき」と言っており,Aの発言からこれは明らかに正しいです.
よってCは正直者となります.
グループ分けの中でCが正直者となっているのは①と④で,ひとまずこれらが候補となります.

つぎにDの発言に注目します.
Cが確実に正直者であることはわかっているので,Dがウソつきかどうかを考えてみます.
①の場合はAはウソつき,CとDが正直者で,Dの発言内容と合致します.
④の場合はAとCが正直者,Dがウソつきとなりますが,これもDの発言内容が嘘ということとなり合致します.

以上より①と④はどちらもあり得るので1つに絞れません.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143607p:plain
ここから確実に言えるのは,「Bがウソつき」「Cは正直者」「正直者とウソつきは2人ずつ」くらいです.
選択肢をみると,5の「ウソつきは2人いる」が正しいことがわかりました.


まとめ

以上がGW法によるウソつき問題の解法になります.
ルールにより機械的に分類作業をすすめ,あとは組み合わせを考えるだけなので,慣れるとかなり高速で解くことができそうです.



余談

A「Aはウソつきだ」

のような,自分について言及するような証言は,ウソつき問題では一般的に含まれません.
これはウソつきのパラドックスだとかエピメニデスのパラドックスとか言われる,自己言及のパラドックスというものの一種になるため回答者に誤解を与えるからだと思われます.
[wiki:自己言及のパラドックス]