次の問題があります。ある山で女の子が立ち往生しており、そこには 2 つの道があります。1 つの道は彼女を救助者 (左折) に連れて行き、2 つ目 (右折) は彼女をジャングルに連れて行き、そこから戻ってくる機会はありません。今、彼女は常に真実を話すnと言う人々のグループに出会い、mは真実を話すかもしれない/しないかもしれないと言う人もいます。n は m より大きいとします。そのため、女の子はランダムな人に尋ねることができます-どちらが救助者であるか、問題は、彼女がどちらに頼んでいるのかわからないことです(nまたはm)。何人の人が真実を語っているかを見つけるための Big Theta (n + m) アルゴリズムがあるかどうか知りたいですか? または厳密に言えばnの値？
これのより単純なバージョンを自分で解決できます。2 人だけだとします。1 人は常に真実を話し、もう 1 人は常に嘘をつきます。彼女は、両方が同じ答えを返すような質問をすることができます。例: 真実の話し手に対して、彼女は尋ねることができます。真実の話者は言うだろう - 右折（相手が嘘をついているから）。今、彼女は嘘つきに同じ質問をすることができます - 彼は言うことで答えます - 同様に右折します (本当の答えは左折ですが、彼はいつも嘘をつくので、彼は右折します)。今、彼女はそれが正しい答えであることを知って、左に歩くことができます.
問題は、最初のケース - 2 番目のグループの人々は嘘をつくかもしれないし、嘘をつかないかもしれないということです。しかし、鍵となるのは n > m ie 常に真実を話す人の数は、真実を話すかもしれない/話さないかもしれない人の数よりも多いということです。だから、これは何かをキャンセルするように見えます。
どんな助けでも大歓迎です。ありがとう。