Which fractions $ \dfrac{p}{q},$ where $p,q$ are positive integers $< 100$, is closest to $\sqrt{2} ?$ Find all digits after the point in decimal representation of that fraction which coincide with digits in decimal representation of $\sqrt{2}$ (without using any table).
Problem
Source: IMO LongList 1967, The Democratic Republic Of Germany 2
Tags: number theory, approximation, decimal representation, rational number, irrational number, IMO Shortlist, IMO Longlist
16.12.2004 22:12
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
17.12.2004 19:46
Consider the Pell's equation $x^2-2y^2=1$ and also the Pell's Negative equation $x^2-2y^2=-1$. Consider the union of this two equations which has solutions ${x_n=\frac{(1+\sqrt 2)^n+(1-\sqrt 2)^n}{2}},y_n=\frac{(1+\sqrt 2)^n-(1-\sqrt 2)^n}{2\sqrt 2}$ Lemma. If $|\frac uv-\sqrt 2|<0.015$ then $\frac{|u^2-2v^2|}{2.85 q^2}<|\frac uv-\sqrt2 |<|\frac{|u^2-2v^2|}{2.b1 q^2}$. Proof: We have ${|\frac uv-\sqrt 2}=\frac{|\frac{p^2}{q^2}-2|}{\frac pq+\sqrt 2}$ and from now it's easy. Now let $p,q$ realize the minimal value of $|\frac pq-\sqrt 2|$. We claim $p=x_n,q=y_n$ or $p=2y_n,q=x_n$ for some $n$. Suppose not. Then $|p^2-2q^2|\neq 1,2 $. Playing with residues we show that $|p^2-2q^2|=3,4,5,6$ has no solutions for $(p,q)=1$. That means $|p^2-2q^2|\geq 7$. Now let $x_n<p<x_{n+1}$ then we easily show $y_n<q<y_{n+1]}$. Since $\sqrt2-\frac 75<0.15$ using the lemma we get $|\frac pq-\sqrt 2|>\frac{7}{2.85 q^2}>\frac 7{2.85 y_{n+1}^2}$. But one easily shows that $y_{n+1}<2.5 y_n$ and using this we show that $|\frac pq-\sqrt 2|>\frac 1{ 2.81 y_n^2}>|\frac {x_n}{y_n}-\sqrt 2|$. Hence $p,q$ are not minimal. Contradiction. So $(p,q)$ are of form $(x_n,y_n)$ or $(2y_n,x_n)$ and we easily investigate this cases.
27.07.2023 21:35