から までの番号が付いた 枚のコインがあり、この中に 枚だけ偽物が混じっていることがわかっています。 あなたは、はじめ 円持っており、 円を支払うことで、支払いが可能である限り何度でも、
と尋ねることができます。 ここで、 は質問の度に毎回自由に選ぶことができ、また、この質問に対しては常に正しい答えが返ってくることが保証されます。 (なお、コインは日本円ではないため 枚のコインの一部を支払いに利用することはできません。) そして、最後に一度だけ「何番のコインが偽物であるか」を宣言することができます。 この宣言が的中していた場合、あなたの勝利となります。
どのコインも偽物である確率が等しい(すなわち、どのコインも の確率で偽物である)と仮定したとき、あなたが最適な質問順と宣言を選ぶと勝利できる確率はいくらでしょうか。
この答えは有理数であることが証明できますので、 で答えてください。 厳密には、答えを既約分数で としたとき、 となる、 以上 未満の整数 を答えてください。
上述の の値を出力してください。
3 2
665496236
あなたは 円持っているため、例えば として「 番以下に偽物があるか」を尋ねることができます。
答えがいいえであれば、 番が確実に偽物です。 このようになる確率は、条件より であり、この場合は確実に勝利できます。
答えがはいであれば、 番または 番が偽物です。 このときあなたは所持金を使い切ってしまっているため、これ以上の質問はできません。 このようになる確率は であり、あなたはどちらかを当てずっぽうに選んで宣言することで、この状況から の確率で勝利できます。 したがって、 番または 番が偽物であり、かつ偶然にも勝利できる確率は となります。
以上より、あなたの勝率は となるので、 では上記の答えになります。
2 0
499122177
質問はできませんが、当てずっぽうな宣言で の勝率が得られます。
5 7
1
あなたは最適な順で質問することで、確実に偽物を特定し、勝利することができます。