個のコインがあって，そのうち１個が偽コインである．その１個のみが重さがちがっている．（重いか軽いかはわかっていない）天秤ばかりを用いてこの偽コインを見つけだしたい．天秤ばかりの使用回数のだいたいの最小値を求めよ．

に対して　　

求める最小値の上限は　　である．

＊　偽コインが軽いとわかっているとき，最小値の上限がであることを示す．

　　コインの個数をとするとき M.Iをもちいる．

（１）のとき，１個ずつ天秤にのせると，つりあうとき残りの１個が

      偽コイン．つりあわないとき，天秤上の軽いほうが偽コイン．

（２）のコインが高々回で偽コインを判別するとき，

　　　のコインが高々回で偽コインを判別することをしめす．

　　　まずのコインを３つのグループにわける．それぞれのグループにはの

　　　コインが所属している．３つのグループの二つを一つずつそれぞれ天秤の両

　　　側にのせる．つりあえばのこりのグループの中に偽コインは含まれる．つり

　　　あわなければ天秤上の軽いグループの中に偽コインは含まれる．いずれにし

　　　ても残りのコインの数はだから，後高々回で偽コインを判別することが

　　　できる．

　以上より　M.Iが完結した．　　

＊＊偽コインが重いか軽いかわかっていない時は，最初の３グループの時点でもう

　　１回違う組み合わせで天秤にかけてみて，偽コインの入ったグループと､その偽

　　コインが重いか軽いかを確定しておいて残りのstepを始める．

　　このときが，問題の場合であって，回行えば偽コインは判別できる．


　　　　　　BACK　HOME