Y箱

100番です。
袋から連続で2個のボールを取り出したときに、同じ色のボールが出る確率をちょうど2分の1にするには、何個のポールを入れたらいいでしょうか。という問題です。

初めに思いついた方法は時間がかかりすぎてだめでした。
式を立てていろいろいじっていたら解けました。


青のボールの数をb、全体のボールの数をaとすると、1つめに青の出る確率は、b/a、その後で2つめも青になる確率は(b-1)/(a-1)です。問題は、これを掛けたものが1/2になる場合ということです。

方法その1

1回目と2回目の確率は、aやbが大きくなるとほとんど同じになり、それぞれ√2に近い値になります。1回目の確率の方が大きいので、あるaに対してbは、「b/aが√2よりちょっと大きくなる」ように決めてやることができます。

ということで作ったのが、最初のコードです。ところが、実行してみると1時間たっても1桁も進みません。5時間ほどぶんまわしてみたのですが、答えが出ません。だいたい、平方根の逆数を使っているので、そんなに桁数が大きいとなると精度に入らない可能性があります。この方法はあきらめました。

ちなみに、小さな数であれば、ちゃんと答えがでます。桁を増やしながら計算してみると、

user> (time (pe100 10N))
"Elapsed time: 0.237575 msecs"
[15N 21N]
user> (time (pe100 50N))
"Elapsed time: 2.299302 msecs"
[85N 120N]
user> (time (pe100 200N))
"Elapsed time: 15.118969 msecs"
[493N 697N]
user> (time (pe100 100000000N))
"Elapsed time: 79792.608028 msecs"
[112529341N 159140520N]


最後のところくらいで1分を超えてしまいます。

方法その2

題意を数式にすると、



のようになります。あれこれいじくりまわしたところ(最初ひどいミスをしていて、1時間くらいハマりました。)、ペル方程式の形に持っていくことができました。



この最後がペル方程式の形です。



ペル方程式は前にも出てきました。あとは最小解さえわかれば、答えがでそうです。
最小解はなんだろうと調べる間もなくが思い付きました。

あとは漸化式に初期値を突っこんで、 を超える最初の値を出すだけです。

答えはX,Yからa,bを出す式を作って計算です。



上が正解で、下が遅いやつです。