IMO 1967 LL GDR14

Origin: GDR

Problem

Which fraction p/q, where p, q are positive integers less than 100, is closest to \sqrt 2? Find all digits after the decimal point in the decimal representation of this fraction that coincide with digits in the decimal representation of \sqrt 2 (without using any tables).

Solution

We have that

p q − \sqrt = |p −q \sqrt 2| q = |p2 −2q2| q(p + q \sqrt 2) \geq q(p + q \sqrt 2), (1) because |p2 −2q2| \geq1. The greatest solution to the equation |p2 −2q2| = 1 with p, q \leq100 is (p, q) = (99, 70). It is easy to verify using (1) that 99 70 best approximates \sqrt 2 among the fractions p/q with p, q \leq100. Second solution. By using some basic facts about Farey sequences one can find that 41 29 < \sqrt 2 < 99 70 and that 41 29 < p q < 99 70 implies p \geq41 + 99 > 100 because 99 \cdot 29 −41 \cdot 70 = 1. Of the two fractions 41/29 and 99/70, the latter is closer to \sqrt 2.