教えてください
found (2005/01/07(Fri) 17:07:05)
はじめまして
いろいろなところで聞く嘘つき村の派生問題なのですが
回数はわかっても具体的な質問が分かりません。
正直村と嘘つき村があり住民はよく似ていて見分けが付かないが，
正直村の住民は質問に対して常に正しい答えを言い嘘つき村の住民は
常に正しくない答えを言う。
正直村と嘘つき村の他に住民の見分けが付かない真ん中村があり住民は
正しい答えと正しくない答えを交互に言う。すべての村の住民に行き来がある。
どれかの村に迷い込んだとき，そこで出会った人に質問をして，
今どの村にいるのかを知りたい。
次のそれぞれの場合に，イエス・ノーが答えになる質問をするとして
具体的にはどのような質問をすればよいか。
自分がいる場所は3 通りで，それがわかるための情報量はlog2 3 ビット
最小2回ででるとは思うのですが
どなたかお力をお貸し下さい<(_ _*)X(*_ _)>
you (2005/01/08(Sat) 17:04:20)
（その村にいる他の人を指さしながら）
「あの人に『ここは正直村ですか？』と聞くと、『イエス』と答えますか？」
あの人＝Ａさんとすると、
?@正直村の場合：
Ａさんは正直に「イエス」と答え、回答者も正直に「イエス」と答える。
?A嘘つき村の場合：
Ａさんは嘘をつき「イエス」と答え、回答者も嘘をつくので「ノー」と答える。
この質問を２回繰り返し、１回目と違う答えだった場合は中間村になる。
斑猫 ◆XMrov1pg (2005/01/08(Sat) 18:51:43)
「すべての村の住民に行き来がある」ので
誰がその村の住民かも特定できないのですね
youさんの答は少し違うと思います
１、「ここは正直村ですかと聞いたらあなたはイエスと答えますか」
２、「ここは嘘つき村ですかと聞いたらあなたはイエスと答えますか」
1にイエスで正直村
2にイエスで嘘つき村
どちらもノーで真ん中村です
you (2005/01/08(Sat) 22:10:52)
> 「すべての村の住民に行き来がある」ので
> 誰がその村の住民かも特定できないのですね
> youさんの答は少し違うと思います
本当だ(笑)
ご指摘ありがとうございます〜。
それを考えると斑猫さんの回答を見てもよくわからなくなってきた…
難しいですね〜!
※ 問題中に使用されている人名、地域名、会社名、組織名、製品名、イベントなどは架空のものであり、実在に存在するものを示すものではありません。
