数学の部屋へもどる◆愛知県 迷子の雄猫 さんからの解答。
【問題１】
１００枚中２５枚を選択できれば良いから、
100Ｃ25＝242519269720337121015504＜２78 で、７８ビット
並べ方は試合開始直前に渡さなくても、事前に作戦として渡せば良い。
（パターン１のときは・・・パターン２のときは・・・パターン１０００のときは・・・（以下略）という形で渡せる）
【問題２】
１００枚中２５枚を選択できれば良いから、100Ｃ25
空きを無視して２５枚を並べて、空きの位置を２箇所送信すると考えて、
25Ｐ25と27Ｃ2
100Ｃ25ｘ25Ｐ25ｘ27Ｃ2 ＜２169.82
つまり合計１７０ビット
【問題３】
まず、自陣の札を100Ｃ25で知らせる。
残りの札は７５枚であるから、７５枚中２５枚を特定するためには、75Ｃ25
この並び方を知らせるには、
0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6の数字２５個の並びを渡せば良い。
25Ｐ25／（4Ｐ4）6
全て掛け算して
100Ｃ25ｘ75Ｃ25ｘ25Ｐ25／（4Ｐ4）6 ＜２199.37
つまり合計２００ビット
◆東京都 やっこざき さんからの解答。
logの底は2とする。
【問題１】
自陣の25枚の札番号のみが特定できればいいので、
送信ビット数は、
log(100C25) = 77.6824456 ですむ。
【問題３】
(1)ロボットは、自陣の25枚を全て知っている必要がある。
自陣に知らない札が1枚でもあると、ゲーム開始直後にその札がよまれて、人間がその札を取り、人間側からロボット側に札が1枚渡ると、 ロボットは渡された札が何であるかわからないのでそれ以降、人間側の陣にどの札が残っているのかはわからない。
したがって、人間側の陣の情報は無効になる。
この後、24枚連続で、人間側の札がよまれれば人間が勝つ。
(2)ロボットは、人間側の25枚を全て知っている必要がある。
人間側の陣の24枚を知っている場合も、常に人間側の陣の札がよまれるとロボットが負ける。
ロボットが人間側の陣の(知っている)札を1枚取ると、ロボットから人間に渡された札がどこに置かれたかロボットにはわからないので、ロボットが知っている人間側の陣の札の数は1枚減る。
したがって、ロボットが24枚人間側の陣から取ると、ロボットは人間側の陣について、全く分からない。
以降も人間側の陣からよまれれば人間が勝つ。
なお、ルールから、常に、人間側の陣には人間が勝つのに十分な枚数が残っている。
(1)(2)より、ロボットは50枚全部を知る必要がある。
自陣の25枚は、常に決まった位置に、小さい順に置けば良い。
自陣にあるのは人間側にない、75枚のうちの25枚である。
結局、
人間の25枚の札の選び方 100C25 通り
25枚を(0)〜(6)のグループに分けるやりかた
25C4*21C4*17C4*13C4*9C4*5C4 通り
求めるビット数は、
log(100C25*25C4*21C4*17C4*13C4*9C4*5C4) = 133.854184
133.854184 + log(75C25) = 199.365566
===> 答え 200ビット
◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】 ７８ビット
作戦として置く位置と順番を打ち合わせておけるので
Ceil[log2(100C25)] で計算できます。
【問題２】 １７０ビット
空きの位置が 27C2とおりあり
Ceil[log2(100Ｐ25*27C2)] で計算できます。
【問題３】 ２００ビット
相手への札引渡しがあるため結局全部覚えなければならず、
Ceil[log2(100Ｃ25)]＋Ceil[log2(75P25/4P46)] となります。
注記）まとめてCeilでも答え同じ
◆ 問題へもどる
◆ 今週の問題へ