◆山梨県 Footmark さんからのコメント。
本物や偽物の重さが判明している場合でさえ、n回で見つけ出すには
2n 枚以下でなければ不可能です。
【証明】
任意の時点で、偽物の候補がm(≧2)枚あるものとします。
その内のあるk(1≦k<m)枚を計測すると、
偽物は「そのk枚の中」か「残りのm−k枚の中」か判明します。
ところが、どちらになるかは計測してみなければ判りません。
ですから、最悪であっても候補を最少にするには、
k= | m 2 | とするのが最善です。 |
その時はどちらであっても候補の半分はあり得ないものとして消去できます。
そこで、n回の計測回数で候補が1つになったものとします。
すると、n回が必要計測回数であり、 | m 2n | ≦1 となります。 |
つまり、m≦2nであり、nで表すと n≧ceil(log2m) です。
ただし、ceil(X)は X 以上の整数で最小のものを表すものとします。
証明終わり。
3回で見つけるには、m≦23 ですから、8枚以下でなけねばなりません。
12枚なら、n≧ceil(log212) ですから、4回以上は必要です。
ですから、本問は不可能です。
◆愛知県 Y.M.Ojisan さんからの解答。
とんち解です。
Footmarkさんが御指摘のようにこの問題は正面攻撃では不可能と思います。
しかし、問題の未知量は本物と偽物の重さの実数値2個と何番目が偽物かの整数値1個の3個です。
これに対し、3回計れるので実数値3個が既知量として得られ、既知量の情報の方が若干上回っています。
そこで本物重さをT、偽物の重さをT+F≠T、
K番目が偽物とし(K=1〜12)、次の方程式を考えます。
(1) (1+2+ 〜 +11+0)T+KF=12W1 K≦11 (1+2+ 〜 +11+0)T =12W1 K=12 (2) (2+3+〜11+1+0)T+(K+1)F=12W2 K≦10 (2+3+〜11+1+0)T+ (1)F=12W2 K=11 (2+3+〜11+1+0)T+ =12W2 K=12この式より もしW1=W2であればK=12です。そうでない場合
(3) (2+3+〜11+0+12)T+(K+1)F=12W3 K≦10 (2+3+〜11+0+12)T =12W3 K=11も考えます。1≦K≦10のとき、(1)〜(3)を解くと
F=12(W2−W1),T= | 12(W3−W2) 11 | & |
K= | 12W1−66T F | = | W1−6W3+6W2 W2−W1 | ――(A) |
でKが判ります。
K=11のとき、この式を計算すると
K= | 66T+11F−6*77T+6F+6*66T −10F | =−1.7 |
で整数ではありません。
以上からK=−1.7と計算されたらK=11です。
実際にバネ秤を使って無理やりこれを実現する方法としては幾つか考えられます。
下図は12分の1単位でバネの途中から糸を垂らし、計る方法です。
コインは穴明きが良い。
精度が実際には出ないかも。
また、12分の1という余分の計測をしているという批判には耐えないですが。
誤差を考えると 下図(1)〜(3)を計測し、
それぞれの計測値をW1、W2、W3として式(A)を四捨五入で計算します。
答えがK=1〜10ならK番目が偽です。
Kが−2か−1ぐらいなら11番目が偽です。
|K|>10なら12番目が偽です。