|
doba |
|
えっと、問題の条件が
・１枚だけ重さが異なる（偽物）。但し、その１枚が他より重いか軽いかわからない ・その１枚を特定できさえすればよい。すなわち、その１枚が他より重いか軽いかは 最終的にわからなくてもよい ということなのであれば、どうもみなさんの答えは違うようなのですが．．．。 私の得た答えは、天秤をn回使って１枚の偽物を特定できる最大の枚数は (3^n - 1)/2 というものです。 nに10を代入すると、29524枚となります。 考え方： 天秤操作を繰り返している途中において、硬貨は次のように分類されます。 タイプＮ：本物であることが確定している。 タイプＨ：もし偽物ならば他より重いが、本物である可能性もある。 タイプＬ：もし偽物ならば他より軽いが、本物である可能性もある。 タイプＸ：偽物であった場合に、軽いか重いかは不明であり、本物である可能性もある。 最初は、全ての硬貨がＸです。 天秤がつり合い続けている間は、ＨやＬは存在せず、１回でも天秤にかけたものがＮ、 １回もかけていないものがＸとなります。 １回でも天秤がつりあわないことがあれば、その時に天秤に乗っていたもののうち Ｎでないものが全てＨまたはＬとなり、他は全てＮとなります。 つまり、ＨやＬと、Ｘは共存しません。 まず、ＨとＬだけ合わせてx枚あるとき、 n回の比較で特定できるようなxの最大値は、3^nです。 実際に、ＨとＬが合わせて3^nあった場合を考えると、 そこから、Ｈを偶数枚、Ｌを偶数枚、合わせて2×3^(n-1)枚選ぶことができます。 それらを、天秤の左右に均等に乗せると、どちらに傾いてもあるいはつり合っても、 １回の比較の結果ＨとＬが合わせて3^(n-1)残ります。 次に、Ｘがx枚と、Ｎが１枚あるとき、 n回の比較で特定できるようなxの最大値をa(n)とおきます。 Ｘが存在する状態で１回の比較を行うと、 つり合えば天秤に乗せなかったＸが残り、 つり合わなければ天秤に乗せたＸがＨとＬに変化するので、 次のような漸化式が成り立ちます。 a(n)＝a(n-1)+3^(n-1) ここで、Ｎが１枚必要なのは、3^(n-1)枚のＸを天秤に乗せる際に、 左右のバランスをとるためです。 また、明らかに、a(1)＝2が言え、この漸化式を解くと、 a(n)＝(3^n+1)/2 となります。 よって、最初に本物の硬貨が別に１個存在していたならば、 n回で特定できる最大値は(3^n+1)/2となります。 実際には１回目にはＮは存在しないので、天秤に3^(n-1)枚乗せることはできず、 天秤に乗せるのが3^(n-1)-1枚で、乗せないのが(3^(n-1)+1)/2枚、 合計(3^n-1)/2枚が最大となります。 |
|
7月3日（火） 8:05:42
30168 |