|
doba |
|
#30181
えっと、ちょっと落ち着きましょう(^^; 確かにa(2)=5ですが、今回の問題の答えとしては２回のとき最大４枚です。 同様に、a(3)=14ですが、今回の問題の答えとしては３回のとき最大13枚です。 直感的（？）に考えても、4*3^(n-2)+1なんて出てきませんよ。 #30168で述べているのは、枚数とは別に正しい重さの硬貨が１枚ある場合の、 n回での最大値をa(n)と定義して、a(n)についての漸化式からa(n)＝(3^n+1)/2を 求めた上で、今回の問題の答えとしてはa(n)より１少ない (3^n-1)/2となる、ということです。 ついでに、１枚の偽物を特定する手順を一般化しておきます。 意味さえわかれば、何もややこしいことはないですよ。 最初に正しい重さの硬貨が別に１枚ある場合であれば、 例外的なケースがなくなるので、もっとシンプルに書けますが、 ここでは、オリジナルの問題の条件で書いています。 場合分けがいっぱいあるように見えますが、 ＨとＬの枚数の組合せの細かい違いについて場合分けしているだけで、 本質的には、Ｘがある場合と、ＨやＬがある場合という大きく２通りの 場合について、やるべきことを理解すればいいだけです。 なお、これは手順の１例にすぎず、天秤に乗せるＨとＬの枚数は、 合計枚数と、左右の組成が同じであることを守れば、どうでも構わないのですが、 ここではなるべく規則的な手順となるように書いています。 実際の作業としては、Ｎ，Ｈ，Ｌ，Ｘの分類毎の袋か箱を用意して、 ステップ毎の硬貨の分類の変遷をきちんと管理する必要があるでしょうね。 特に、天秤に載せる時に混ざらないようにしないと(^^; （なんせ、３万枚近くありますから．．．。） ＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠＠ (3^n-1)/2枚から偽物をn回で見つける手順 最初Ｘ：(3^n-1)/2枚 【１回目】 ［Ｘ：(3^(n-1)-1)/2枚］vs［Ｘ：(3^(n-1)-1)/2枚］ ＝のとき：乗せてないＸ：(3^(n-1)+1)/2枚が残り、他は全てＮ ＞のとき：左のＸ：(3^(n-1)-1)/2枚→Ｈ、右のＸ：(3^(n-1)-1)/2枚→Ｌ、残りは全てＮ ＜のとき：左のＸ：(3^(n-1)-1)/2枚→Ｌ、右のＸ：(3^(n-1)-1)/2枚→Ｈ、残りは全てＮ 【ｋ回目（２≦ｋ≦ｎ）】 ・Ｘが(3^(n+1-k)+1)/2枚、残りが全部Ｎの場合 （k-1回目まで毎回「＝」の場合） ［Ｘ：(3^(n-k)+1)/2枚］vs［Ｘ：(3^(n-k)-1)/2枚，Ｎ１枚］ ＝のとき：乗せてないＸ：(3^(n-k)+1)/2枚が残り、他は全てＮ ＞のとき：左のＸ：(3^(n-k)+1)/2枚→Ｈ、右のＸ：(3^(n-k)-1)/2枚→Ｌ、残りは全てＮ ＜のとき：左のＸ：(3^(n-k)+1)/2枚→Ｌ、右のＸ：(3^(n-k)-1)/2枚→Ｈ、残りは全てＮ ・Ｈが(3^(n+1-k)+1)/2枚、Ｌが(3^(n+1-k)-1)/2枚、残りが全部Ｎの場合 ［Ｈ：(3^(n-k)+1)/2枚，Ｌ：(3^(n-k)-1)/2枚］vs［Ｈ：(3^(n-k)+1)/2枚，Ｌ：(3^(n-k)-1)/2枚］ ＝のとき：乗せてないＨ：(3^(n-k)-1)/2枚とＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ ＞のとき：左のＨ：(3^(n-k)+1)/2枚と右のＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ＜のとき：右のＨ：(3^(n-k)+1)/2枚と左のＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ・Ｈが(3^(n+1-k)-1)/2枚、Ｌが(3^(n+1-k)+1)/2枚、残りが全部Ｎの場合 ［Ｈ：(3^(n-k)-1)/2枚，Ｌ：(3^(n-k)+1)/2枚］vs［Ｈ：(3^(n-k)-1)/2枚，Ｌ：(3^(n-k)+1)/2枚］ ＝のとき：乗せてないＨ：(3^(n-k)+1)/2枚とＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ＞のとき：左のＨ：(3^(n-k)-1)/2枚と右のＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ ＜のとき：右のＨ：(3^(n-k)-1)/2枚と左のＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ ・ＨとＬがともに(3^(n+1-k)-1)/2枚、残りが全部Ｎの場合 （ｋが偶数で、１回目が「＞」か「＜」で、２回目以降ずっと「＝」の場合） ［Ｈ：(3^(n-k)+1)/2枚，Ｌ：(3^(n-k)-1)/2枚］vs［Ｈ：(3^(n-k)+1)/2枚，Ｌ：(3^(n-k)-1)/2枚］ ＝のとき：乗せてないＨ：(3^(n-k)-3)/2枚とＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ ＞のとき：左のＨ：(3^(n-k)+1)/2枚と右のＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ＜のとき：右のＨ：(3^(n-k)+1)/2枚と左のＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ・Ｈが(3^(n+1-k)-3)/2枚、Ｌが(3^(n+1-k)+1)/2枚、残りが全部Ｎの場合 （ｋが奇数で、１回目が「＞」か「＜」で、２回目以降ずっと「＝」の場合） ［Ｈ：(3^(n-k)-1)/2枚，Ｌ：(3^(n-k)+1)/2枚］vs［Ｈ：(3^(n-k)-1)/2枚，Ｌ：(3^(n-k)+1)/2枚］ ＝のとき：乗せてないＨ：(3^(n-k)-1)/2枚とＬ：(3^(n-k)-1)/2枚が残り、他は全てＮ ＞のとき：左のＨ：(3^(n-k)-1)/2枚と右のＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ ＜のとき：右のＨ：(3^(n-k)-1)/2枚と左のＬ：(3^(n-k)+1)/2枚が残り、他は全てＮ |
|
7月4日（水） 1:12:17
30182 |