Project Euler Problem100　#ProjectEuler

Project EulerのProblem100に挑戦しました。
ようやく100問目です。
2010/8/16に第1問目に挑戦し、5/8に100問目到達しました。実に265日かかってます。
300問とか、いつになることやら・・orz、最近ちょっと疲れ気味。
とりあえず、無理せず、気長に進めていければと考えています。

---

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)(14/20) = 1/2.
The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.
By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
(日本語訳)

---

　節目の100問目です。数値的に総当たりは無理そうと考え、地道に解き方を考えました。
　青い円盤の数をb、全ての円盤の数をnとすると、確率が50%のなる場合b(b-1)/n(n-1)=1/2の式が成り立ちます。
　この式は、2(b^2-b)=(n^2-n)　→ 2(4b^2-4b-1)=(4n^2-4n-1)-1となり、x=2n-1、y=2b-1とおくと、先の式は・・・・
　　x^2-2y^2=-1
　ということで、前にも出てきたペル方程式となります。
　ペル方程式の一般解はつぎの漸化式で求められます。（x1、y1は最小解）
　　　　　　xn+1 = x1・xn + M・y1・yn
　　　　　　yn+1 = y1・xn + x1・yn
　今回、最小解は[3,2]、M=2なので、xn+1,yn+1は以下の式で求められると考えられます。
　　xn+1 = 3*xn + 2*2*yn
　　yn+1 = 2*xn +3*yn
　これより、円盤の数が10^12を越えた時の青い円盤の数を求めることで解答を得ました。

PEProblem100.java

class PEProblem100 {
	public static void main(String[] args){
		long ox=1;
		long oy=1;
		long blue=0;
		while(true){
			long nx=(long)(3*ox+4*oy);
			long ny=(long)(2*ox+3*oy);
			long b=(ny+1)/2;
			long n=(nx+1)/2;
			if(n>1e12){
				blue=b;
				break;
			}
			ox=nx;
			oy=ny;
		}
		System.out.println(blue);
	}
}

Related posts:

1. Project Euler Problem88　#ProjectEuler
2. Project Euler Problem71　#ProjectEuler
3. Project Euler Problem72　#ProjectEuler
4. Project Euler Problem87　#ProjectEuler
5. Project Euler Problem77　#ProjectEuler