ｸｲｽﾞ一覧 [ｸｲｽﾞ大陸]

No. 5≫ No.6 ≫No. 7

ボムボム 2010/06/11 22:24

＞nn)/さん

「真の」最小比較回数ということは、「証明されている」ということでしょうか？
僕個人としては
「うまーく考えるとm回まで下げられるんじゃないか」
と期待してしまうのですが、上記のとおりだとしたら残念です…(;v;)
参考になる資料があったのでしたら、できればそのソースを教えていただけたらと思います (*^_^*)

挙げられている数字を見ると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通りまで減らせて…とか。そこから先が想像を絶します。