Euler Problem 100


Euler Problem 100: Finding the number of blue discs for which there is 50% chance of taking two blue.

Rješenje:

Potrebno je pronaći broj plavih diskova, čiji ukupan broj diskova prelazi 10^{12} . Ako pretpostavimo da je:

b – broj plavih diskova,
d_{u} – ukupan broj diskova većih od  10^{12}

Sada imamo sljedeću situaciju. Vjerojatnost da izaberemo dva plava diska možemo izračunati na sljedeći način analogno kao i u opisu problema:

\frac{b}{d_{u}}\cdot \frac{b-1}{d_{u}-1}=\frac{1}{2}

Odnosno nakon sređivanja izraza dobijamo:

2b(b-1)=d_{u}(d_{u}-1)

Sada je potrebno ovaj izraz svesti na Pell-ovu jednačinu i tražiti prvo rješenje.  Ako izraz pomnožimo sa 4, dobijamo sljedeće:

8b(b-1)=4d_{u}(d_{u}-1)

2(4b^{2}-4b+1-1)=4d_{u}^{2}-4d_{u}+1-1

2(2b-1)^{2}-2=(2d_{u}-1)^{2}-1

Sređivnjem jednačine imamo:

(2d_{u}-1)^2-2(2b-1)^2=-1

Izraz smo transformirali u oblik koji je pogodan da se uvede dodatna smjena.

x=2d_{u}-1, y=2b-1

Izraz prije uvođenja smjene sada poprima oblik:

x^2-2y^2=-1

Zadnji izraz predstavlja Pellovu jednačinu, koja se sada rješava standardnom metodom. Vrlo lako ovu jednačinu možemo riješiti preko Mathematica, ili nekom od već urađenih implementacija kontinualnih frakcija za rješevanje Pellove jednačine.

Implementacija u Mathematica:

Clear[sol,x,y,n];
sol=y/.FindInstance[x^2-2 y^2==-1&&x>10^12&&y>0,{x,y},Integers][[1]];
FindInstance[2 b-1==sol&&b>0,{n},Integers]

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 09/03/2010, in Project Euler and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s