- 635 名前：１３２人目の素数さん mailto:sage [[ここ壊れてます] .net]
- 次は回答者のターン。
・ 回答者は、出題者から渡された t^{1},t^{2},…,t^{100} を用いて時枝戦術を実行する。
・ 具体的には、回答者は番号1,2,…,100の中からランダムに番号 i を1つ選ぶ。
・ 次に、回答者は100列に分解された可算無限個の箱のうち、i列目以外の全ての箱を開ける。
・ j≠iとして、j列目の箱の中身は s^{j} である。回答者は t^{j} を所持しているので、
t^{j}−s^{j} を計算することで多項式 f_j(x) を復元できる。
・ s^j の決定番号 d(s^j) について、d(s^j) ＝ deg f_j(x) ＋ 1 が成り立つので、
回答者は99個の決定番号 d(s^j) (j≠i) を得る。そこで、D ＝ max{d(s^j)｜j≠i} と置く。
・ 回答者は t^{i} が欲しい。そこで、i 列目の箱のうち(D＋1)番目以降の箱を開けて、……とする必要はない。
なぜなら、回答者は既に t^{i} を所持しているからだ。特に、回答者は t^{i}_D の値を直ちに取得できる。
・ そこで、回答者は「 i 列目のD番目の箱の中身は t^{i}_D である」と推測する。
・ この推測がハズレになるのは、D ＜ d(s^i) が成り立つときのみで、
そのような i は1,2,…,100 の中に高々1個しかない。よって、回答者の勝率は 99/100 以上である。
|
 |
