19/07/30 14:01:04.63 elHfUa7y.net
『n枚の金貨がある(n≧2).
この金貨の中に1枚だけ重さの違うものが混ざっているが,
それは他のものと見分けがつかない.
天秤を4回使っても, 重さの違う金貨を特定出来ないという.
このときnの最小値を求めよ』
■重さの違う金貨を特定出来る最大値は40
天秤に1枚づつ以上載せて釣り合えばその金貨は
正式な金貨であることが確定する
最初に13枚づつ載せて釣り合えばこの26枚は正式が確定
残り14枚の中にニセ金貨がある
傾けばこの26枚の中にニセ金貨がある
ニセを含む14枚の内、9枚と正式な金貨9枚を比べる
釣り合えば残り5枚の内の3枚を情報が確定している
正式な金貨と比べる
釣り合えば残り2枚の内の1枚を情報が確定している
正式な金貨と比べればニセが確定
3枚が釣り合わなければ『重いか軽いかが確定している3枚』
となるので次の一回で確定する
ニセを含む9枚と正式な金貨9枚が釣り合わなければ、
『重いか軽いかが確定している9枚』となるので
次の二回で確定する
13枚づつ計26枚が傾けば、どちらかに
重いか軽いかの金貨がある
この場合、互いの13枚から4枚づつをエクスチェンジする
そこに情報確定済みの正式な金貨を片側に9枚加えて
13枚づつを計る
釣り合えば正式な金貨9枚の代わりに取り除いた
9枚の金貨が『重いか軽いかが確定している9枚』となるので
次の二回で確定する
傾きが逆になったときはエクスチェンジした金貨がニセ
この4+4枚の金貨でさらに1枚づつのエクスチェンジを行う
すると
『重いか軽いかが確定している3枚』と『重軽どちらかがある2枚』
となるので、次の一回で確定する
傾が変化しなければエクスチェンジしなかった9枚の金貨が
『重いか軽いかが確定している9枚』となる
これらの時、ニセ金貨が重いか軽いかも自動判定される
（ただし、『重軽どちらかがある2枚』は50％の確率でニセという
情報のみ判定）
金貨41枚だとさらに1回の調査が必要になる
以上により、
重さの違う金貨を特定出来ないnの最小値は41.