Euler Problem 100

Posted on by

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]
Advertisement

Leave a Reply

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

Gravatar
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 )

Cancel

Connecting to %s