FAQ
RSS
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（2人）
算数・数学クイズ
算数・数学クイズ
天秤パズル
答え不明
広告
クイズ大陸関連書籍
|
|
ツイート
|
 重さの異なるN枚のコイン
難易度：★★★
 るーびっく
2010/06/10 00:51
自分で問題を考えて、自分で解けなくなってしまった問題です…
 そして、このサイトのみなさんの力をお借りしたく投稿させて頂きます。 重さの解らないN枚のコインがあり、全てのコインの重さはバラバラです。 これに、天秤を用いてN枚のコインの重さの順番を知りたい。 では天秤を何回使用すれば、全てのコインの順番を決定出来るでしょうか？という問題です。 ある程度は自分でも推測出来たのですが、「それが最善手であるのか？」という検証をどうすれば良いのか解らなくなってしまいました。 例えば天秤の左右に１枚ずつ載せて測る場合、３枚のコインであれば、３回必要なことが解ります(勿論、運次第では２回で決定出来るけれども、あらゆるパターンを想定して)。４枚のコインの場合を考えれば、３枚のコインの重さが解った状態から＋２回天秤を使用すれば良く、またコイン５枚であればさらに＋３回。コイン６枚の場合はそこから＋３回。 すなわちｋ－１枚の重さの解っているコインがある場合、さらに１枚のコインがどこの順位に入るかを考えれば、２^(ｍ－１)＜ｋ≦２＾ｍ を満たすｍ回の試行で次の１枚の順位を決めることは可能かとは思うのですが…。そうやって測っていくことが、最短手が否かが解らず…上述の方法の検証ないし、又他に最善手があるならどういう方法か？を見つけ出してほしい…ということです。
|
回答募集は終了しました。
|
N 枚のコインの並び方は N! 通りあるので，天秤でどちらが重いか m 回判定して
どの順列か確定するためには，2^m ≧ N! が成立する必要がある． つまり，最悪ケースで最低必要な回数は m = [log_2 N!] ([ ] は切上げ関数) である． N: 2, 3, 4, 5, 6, 7, 8, 9,10 m: 1, 3, 5, 7,10,13,16,19,22 オーダ評価すれば m = O(N log N) であり，ヒープソート算法で実現できる． 簡単にいえば，敗者復活式トーナメントを組むようなものである． 
Help 問題なので囁かなくてもよさそうですが，
一応そちらに書いておきます． 
るーびっく
コメント有難うございます！
 えーと、勝手に公開してしまいましたが宜しかったでしょうか？ 確かにそういう風に考えていけば、「この回数より少ない回数では無理」というのは解ると思うのです。 けれども「方法論」を考えると、例えばN＝５のときでも天秤の使用回数はおそらく８回必要になってくると思うのです(問題文でのように。) 2^m ≧ N! を満たすことは必要条件ではあるけれども、十分条件とは言えないと思うんです、そこで悩んでたり 
そうですね．求められているのは，必要十分条件でした．
十分条件はマージソートを考えれば出てきます． N 枚のコインを順位づけるために要する最大の比較回数を n = f(N) と書けば， f(1) = 0 として， N が偶数のとき，f(N) = 2 f(N/2) + N - 1 N が奇数のとき，f(N) = f((N+1)/2) + f((N-1)/2) + N -1 です．具体的には， N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69 で，m = [log_2 N!] との間に必要十分条件があるはずです． ちゃんと考えていませんが，この n が必要十分条件かもしれません．←本当にちゃんと考えてませんね．
るーびっく
コメントどうもですｍ（＿ ＿）ｍ
数式を見てしばらく 。 。 / ／ ﾎﾟｰﾝ ( Д ) となってましたがマージソートをググってみて、何となく式の意味は理解出来てきました。その数値と、問題文で書いた方法で出てくる数値はおそらく同じになると思います、式で書くならば、 n＝Σ[k＝1～N]ceil(log_2 k) (切り上げ関数[]がガウス記号とややこしかったので、ceilと表記しました。)となるかと。 そうですね、ceil(log_2 N!)≦x≦Σ[k＝1～N]ceil(log_2 k)の範囲には絞れると思います、そこから１つの値に特定出来ないかな…という感じです、ボムボムさんのコメントも含めてもうちょい考えてみます。 5枚のときについて。
①適当に二つとって載せる。 軽い方をa、重い方をbとする。 ②ab以外の残りの三つから適当にとって二つ載せる。 軽い方をc、重い方をdとする。 ③aとcを比べる。 軽い方をaとする。 軽い方がcだった場合は、aとc、bとdを入れ替えて名前を付け直せばよい。 ここまでで、a＜b、c＜d、a＜cと分かる。 ④cとeを比べる。 (④-1)c＜eのとき（a＜b、a＜c＜e、c＜d） dとeを比べる(⑤)。 (④-1-⑤-1)d＜eのとき（a＜b、a＜c＜d＜e） bとdを比べる(⑥)。 (④-1-⑤-1-⑥-1)b＜dのとき（a＜b＜d、a＜c＜d＜e） 考えられるのはa＜b＜c＜d＜e、a＜c＜b＜d＜eだから、bとcを最後に比べる。 (④-1-⑤-1-⑥-2)b＞dのとき（d＜b、a＜c＜d＜e） 考えられるのはa＜c＜d＜b＜e、a＜c＜d＜e＜bだから、bとeを最後に比べる。 (④-1-⑤-2)d＞eのとき（a＜b、a＜c＜e＜d） bとeを比べる(⑥)。 (④-1-⑤-2-⑥-1)b＜eのとき（a＜b＜e、a＜c＜e＜d） 考えられるのはa＜b＜c＜e＜d、a＜c＜b＜e＜dだから、bとcを最後に比べる。 (④-1-⑤-2-⑥-2)b＞eのとき（e＜b、a＜c＜e＜d） 考えられるのはa＜c＜e＜b＜d、a＜c＜e＜d＜bだから、bとdを最後に比べる。 (④-2)c＞eのとき（a＜b、e＜c＜d、a＜c） aとeを比べる(⑤)。 (④-2-⑤-1)a＜eのとき（a＜b、a＜e＜c＜d） bとcを比べる(⑥)。 (④-2-⑤-1-⑥-1)b＜cのとき（a＜b＜c、a＜e＜c＜d） 考えられるのはa＜b＜e＜c＜d、a＜e＜b＜c＜dだから、bとeを最後に比べる。 (④-2-⑤-1-⑥-2)b＞cのとき（c＜b、a＜e＜c＜d） 考えられるのはa＜e＜c＜b＜d、a＜e＜c＜d＜bだから、bとdを最後に比べる。 (④-2-⑤-2)a＞eのとき（a＜b、e＜a＜c＜d） bとcを比べる(⑥)。 (④-2-⑤-2-⑥-1)b＜cのとき（a＜b＜c、e＜a＜c＜d） 考えられるのはe＜a＜b＜c＜dだけ。 (④-2-⑤-2-⑥-2)b＞cのとき（c＜b、e＜a＜c＜d） 考えられるのはe＜a＜c＜b＜d、e＜a＜c＜d＜bだから、bとdを最後に比べる。 いずれにしても七回で可能だと思います。
5枚の場合に関してです
るーびっく
コメント有難うございます！
、おお７回でいけますかね！？ちょいと検討する時間を下さい。あと…お疲れ様でした…＾＾；これ大変ですよね…。 最初の時点としては５！＝１２０の可能性があり、a＜b、c＜d→a＜cと比較していく限りは、綺麗に可能性を２等分していけるので、３回目の試行終了時点で、考え得る可能性は１２０÷２÷２÷２＝１５通りですね。うむ、数値的に考えればここから後４回の試行で、不可能ではないですね でもその後が追い付けてないのでちょっと待って下さい＾＾；あと、こちらも遠慮なく公開させて頂きます。非公開希望の方が居られたら囁き内で知らせてくれれば幸いですｍ(_ _)ｍ
こんちはっす(`・ω・´)
自分でも確認してみましたが、５枚のとき７回の試行で決定出来そうですね。４回目以降の場合分けがかなりグロかったですが  ３回試行終了時にa,b,c,d,の４枚の並びは、[a＜b＜c＜d]、[a＜c＜b＜d]、[a＜c＜d＜b]、の３通り、ここにeの入り方がそれぞれ５通りあるので計３×５＝１５通り。 ここでcとeを比較すると、c＜eのとき８通り、e＜cのとき７通りに分割出来るんですね、これは気づきませんでした。そこからボムボムさんのコメント見ずにやってみましたが、同じように分割していけました ということで…、終わり…？な気が若干しなくもないですが、質問者自身はとりあえず、５枚を７回で出来る！というのと、マージソートたるものを知れたことでお腹いっぱいな感じであったり( ´ ▽ ` )有難うございました！ ただ５枚のときは数値的には最小と考えられる、ceil(log_2 5!)＝７回の試行でいけた訳ですが、ではこれを一般化して任意のN枚のときでも ceil(log_2 N!)回の試行で測定する方法があるのか？という検証はしてみたい気がします。 もし出来るのであれば、完全解決であると思います。出来なければ一般化するのは困難な気がしますが、とりあえず、可能か不可能かの議論余地のために、もうしばらくロックせず残しておこうと思います。
どうも難しい問題なようですので，ネットで調べてみました．
2007 年現在で知られている真の最小比較回数 a(N) (N= 2, 3, ..., 14, 20, 21, 22) を m(N) = ceil(log_2 N!), n(N) = Σ[k＝1～N]ceil(log_2 k) と並べました． N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 20, 21, 22 a: 1, 3, 5, 7,10,13,16,19, 22, 26, 30, 34, 38, 62, 66, 71 m: 1, 3, 5, 7,10,13,16,19, 22, 26, 29, 33, 37, 62, 66, 70 n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 69, 74, 79 m と n の間にあって，知られている範囲では，m に等しいか +1 です． これ以外の N について a(N) が求まれば，論文が書けるのではないでしょうか． 追記: Ford-Johnson アルゴリズムを用いれば，比較回数 N ceil(log_2(3N/4)) - [2^[log_2(6N)]/3] + [log_2(6N)/2] で整列できるとのことです．なお，[ ] はガウス記号です． 上記の範囲では全て a(N) に一致します．ただし，N がある程度以上大きい とき (N ≧ 47 ?) には，もっと良い方法があるらしいです．
＞nn)/さん
「真の」最小比較回数ということは、「証明されている」ということでしょうか？ 僕個人としては 「うまーく考えるとm回まで下げられるんじゃないか」 と期待してしまうのですが、上記のとおりだとしたら残念です…  参考になる資料があったのでしたら、できればそのソースを教えていただけたらと思います  挙げられている数字を見るとmと一致していない最小がN=12… この枚数で、なんとか人間の頭で頑張れないかと思ってしまう… でも12!=479001600通り… 気になるのは、 「あるNでmより大きくなっても、そのNより大きなNでmに等しくなることがある」 ことです。 これはNの最小比較回数を考えるのに、例えば "N-1枚に1枚加えた場合は…" のような考え方ではうまくいかない場合があるということ…？
るーびっく
５枚のときに、5!＝120＜2＾7＝128 となんかギリギリ(？)で可能だったので、どんなパターンでも出来そうな気がしたんですけど駄目なんですかね
非数学的な考え方かもしれませんが。 m＝ceil(log_2 N!)の増加の仕方が不規則なのが何とも言えない感じです。N=10,11,12で比較すると、m＝22→(+4)→26→(+3)→29 とか階差減るときとかありますし。 ちなみにN＝6、7、8まではN＝5で7回のところから、問題文で最初に書いたようにやっていけば、m(N)回で測定出来ることは容易に証明出来そうですね。N＝5のときの手法がエグかったので、そこから考えるとモヤッとしますけれど。 12枚でも一応、限界までニ等分していけることはしていけると思うんです(最善手かは不明)。10回の試行で、12!/2^10＝467775通りまで減らせて…とか。そこから先が想像を絶します。
↑ボムボムさん 「証明されている」ということです．
面白いサイトを見つけました． The On-Line Encyclopedia of Integer Sequences で，いろいろな整数列を集めてあり、この A036604 にあります． 参考文献も載っていますから，詳しくはそれらをご覧下さい． また，知られている上限（十分条件）も A001768 にあります. URL: http://www.research.att.com/~njas/sequences/A036604
るーびっく
ほむほむ、夕方に覗いていて出典は僕も気になって居ました。
 何か雰囲気見た感じだけですけど、N：15~19、23以降については、それが最小回数(必要十分)であるかの証明はされてないってことなんでしょうかね。また暇なときに僕もじっくり読んでみます。そもそもソートアルゴリズムというものを知らなかったもので、その辺りも含めて色々勉強になりました とりあえず、そこに乗っていたもの(最低回数かは未証明のもの？)も含めてN:1~30まで下記に纏めてみました。 a'(N): 0, 1, 3, 5, 7, 10, 13, 16, 19, 22 | 26, 30, 34, 38, 42, 46, 50, 54, 58, 62 | 66, 71, 76, 81, 86, 91, 96, 101, 106, 111 m(N) : 0, 1, 3, 5, 7, 10, 13, 16, 19, 22 | 26, 29, 33, 37, 41, 45, 49, 53, 57, 62 | 66, 70, 75, 80, 84, 89, 94, 98, 103 ,108 n(N) : 0, 1, 3, 5, 8, 11, 14, 17, 21, 25 | 29, 33, 37, 41, 45, 49, 54, 59, 64, 69 | 74, 79, 84, 89, 94, 99, 104, 109, 114, 119
とりあえず、質問者的にはスッキリしたので、緑色のヤツ(？)にしときます
皆様有難うござましたｍ(_ _)ｍ 後でもうちょい纏めてみようと思います。 追記；纏めると言いつつ、なんかこれ以上どう纏めて良いか解らなくなってきました…(^q^)、 というかnn)/さんとボムボムさんのコメントでしっかり纏まってるような。 ↓N=12のときに、m(N)回で判別出来ることを言うよりもm(N)回で判別出来ないことを 証明する辺りがかなり大変そう…。 |
問題へジャンプ