2010年1月26日

自問自答

iPhone のアプリ ChessQuizz はタクティクスの問題が360問あり、毎回ランダムに問題を選ぶので、全部の問題を目にするには相当な回数を要します。過去に同じ問題を解いたかどうかを考慮してくれないので、同じ問題を既に何度も見ています。今は自分が解いた問題番号を記録していて、全問制覇ができたかどうか分かるようにしています。そうすると、気になってくることが一つあります:

全問制覇するまでにおおよそ何回かかるか?

自分で思い付いたこの数学の問題が気に入ってしまい、自力で解くことにしました。高校の授業でこの手の問題を最後に解いてから20年以上が経過しているので、公式等はほとんど覚えていません。パズルのつもりで解いてみました。私の答えは約2327回です。以降にどのように解いたかを解説していますが、これを面白いと感じる人はあまりいないでしょうね ...

-----

x は、既に一度は見たことのある問題の数とします(同じ問題は何回出題されても1問と数えます)。
y は、既に一度は見たことのある問題の数が x 問に到達した時点で、まだ見たことのない問題が次に登場するまでにかかるおおよその回数とします。

開始時点では問題を1問も見ていないので x=0 です。x=0 の時、ChessQuizz は見たことのない問題を必ず1回で出すはずなので、y=1 になります。

次は、既に1問を見ているので x=1 です。ChessQuizz が私がまだ一度も見たことのない問題を次に出してくれる確率は 359/360 ですからほぼ1回で出ると思われますが、同じ問題が登場する確率も 1/360 あるので、y の値はほんのわずかだけ 1 よりも大きい値になります。

ChessQuizz の問題を半分(x=180)見た時点では次に新しい問題を目にする確率は 50% ですから、y=1.5 です(1~2回で初めて見る問題が出題される)。

このように続けていき、358問まで制覇した(x=358)とすると、ラスト2問のうちのいずれか1問を目にする確率は 2/360 なので、それならば180回やればどちらか1問に遭遇することが期待できます。

そして、359問まで制覇した(x=359)とすると、最後の1問を目にする確率は 1/360 なので、だいたい360回やれば ChessQuizz がラスト1問を出してくれるだろうという意味で y=360 になります。

上記の x と y の関係を数式で表すと、y=360/(360-x) になります。本来ならばこの式は論理的に導き出せるのでしょうが、私の場合、上記のパターンと辻褄が合うような都合の良い式(例えば、x=0 の時に y=1 となり、x=180 の時に y=1.5 となり、x=359 の時に y=360 となる)を試行錯誤して見つけただけです。



私が求めようとしている全問制覇するまでに要するおおよその回数は y の値の総和になります。数学っぽく表すとこんな感じ:



ちなみに、このような数式をワープロ(Word)で書いたのは初めてですが、これが最後になる気がします。ワープロを使うと綺麗ですが、手で書いた方が圧倒的に効率が良いです。数学者とかはどうしているんでしょうね?

このような表記にしても計算はできないので数式に値を投入して展開します。

360/(360-0) + 360/(360-1) + 360/(360-2) + … + 360/(360-358) + 360/(360-359)

これを計算しやすいように単純化していくと

= 360/360 + 360/359 + 360/358 + … + 360/2 + 360/1

= 360 (1/360 + 1/359 + 1/358 + … + 1/2 + 1/1)

= 360 (1/1 + 1/2 + 1/3 + … + 1/359 + 1/360)

ここまで単純化しましたが、これをどう計算すればいいか分かりません。括弧の内側を簡単に求められるような法則があればいいのですが。例えば 1 + 2 + 3 + … + 359 + 360 なら、合計が 361 になるペアが180組できるので 361×180 で求められますが、そのように計算を単純化できるような規則性が見つけられません。ネックなのは分数だという点です。分母を無理やり統一させようとしたら、1 × 2 × 3 × … × 359 × 360 を分子と分母のそれぞれに掛けるしかありませんが、数字が天文学的になるだけで計算は無理です。相当試行錯誤しましたが、無理っぽいので、グラフ化してみて、グラフの形状で判断することにしました。

(1/1 + 1/2 + 1/3 + … + 1/359 + 1/360) の部分を次のような式にして



グラフ化してみました。



形状が非常に良く似ているのは y=log(x) ですが(私に思いつく似たような他の数式に比べて)、やはり別物です。

ここで式を単純化することは諦めることにしました。諦めてどうするかというと、360 (1/1 + 1/2 + 1/3 + … + 1/359 + 1/360) という計算を Excel にさせるだけです。その結果得られたのが 2327.294859 という数字です。

1 コメント:

kawanaka さんのコメント...

この投稿の続きです(目立つ必要がないのでわざとコメントにしています)。自力で答えを出した後、もっと簡単に計算する方法はなかったのかどうか調べました。まずは数学の公式のサイトを幾つか訪問しましたが、Σ(i)はあってもΣ(1/i)は見つけられませんでした。その後、これは360種類のトレーディング・カードをすべて集めるのと同じことだと気付きました。その分野で検索をかけたら、同じような計算を試みているサイトが見つかりました。それらのサイトでは私と同じ式を使っていますが、私のようにΣ(1/i)の簡略化は試みておらず、いきなり答えを出しています。Σ(1/i)の演算はとても紙と鉛筆で行なえるような代物ではなく、Excel等を使って計算させるしかなかったようです。

コメントを投稿