Maths Olympiad Prep

Library / /6 of 10

Algebra Difficulty 6.2 National Olympiad Find the answer Italy

Problem:

Archimedes knew well that π3,1416\pi \approx 3,1416 can be approximated from above by the fraction 22/73,142922 / 7 \approx 3,1429 and that at least the first two decimal digits are correct.
For how many pairs of integers (m,n)(m, n), with 1<n<1001<n<100, does the decimal expansion of the fraction mn\frac{m}{n} start exactly with 3,14?

Pick one

Solution

Solution:

The answer is (C)\mathbf{( C )}. We need to count the pairs (m,n)(m, n) such that 314/100m/n<315/100314/100 \leq m / n < 315 / 100. Equivalently, we want to determine how many pairs (m,n)(m, n) there are such that 14/100(m3n)/n<15/10014 / 100 \leq (m-3 n) / n < 15/100. Let us define k=m3nk = m - 3 n and count the pairs (k,n)(k, n) such that 14/100k/n<15/10014 / 100 \leq k / n < 15 / 100. Since n<100n < 100, k<15n/100<15k < 15 n / 100 < 15. Let us therefore consider separately the cases k=1,2,,14k = 1, 2, \ldots, 14. For each such kk, rewriting the inequalities, we want to count how many integers n<100n < 100 satisfy
10015k<n10014k \frac{100}{15} k < n \leq \frac{100}{14} k
that is
k3<(n7k)k7 -\frac{k}{3} < (n - 7 k) \leq \frac{k}{7}
So it suffices to count, for each of these intervals (k/3,k/7](-k / 3, k / 7], how many integers they contain. For k=1,2,3,,14k = 1, 2, 3, \ldots, 14 we have respectively 1,1,1,2,2,2,4,4,4,5,5,5,6,71, 1, 1, 2, 2, 2, 4, 4, 4, 5, 5, 5, 6, 7. However, for k=14k = 14, we are not allowed to count n=100n = 100. Thus the answer is 31+32+34+35+6+71=483 \cdot 1 + 3 \cdot 2 + 3 \cdot 4 + 3 \cdot 5 + 6 + 7 - 1 = 48.

Second solution. As above, we want to count the pairs (m,n)(m, n) such that 314/100m/n<315/100314/100 \leq m / n < 315 / 100. We are thus counting the number of points with integer coordinates (m,n)(m, n) in the plane subject to the conditions:
314n100m0,315n100m>0,0<n<100. 314 n - 100 m \leq 0, \quad 315 n - 100 m > 0, \quad 0 < n < 100.
The points satisfying these conditions form a triangle with vertices O=(0,0)O = (0, 0), A=(314,100)A = (314, 100), B=(315,100)B = (315, 100), including the segment OAOA, but excluding the other two. The points with integer coordinates lying inside a segment having one vertex at the origin are the multiples of the pair of coordinates of the other vertex, once reduced to lowest terms. Thus for OAOA there are MCD(314,100)1=1\operatorname{MCD}(314, 100) - 1 = 1, for ABAB there are MCD(315314,100100)1=0\operatorname{MCD}(315 - 314, 100 - 100) - 1 = 0, for OBOB there are MCD(315,100)1=4\operatorname{MCD}(315, 100) - 1 = 4. By Pick's theorem applied to the triangle OABOAB,
a=i+b21 a = i + \frac{b}{2} - 1
where a=100(315314)/2a = 100 \cdot (315 - 314) / 2 is the area of OABOAB, ii is the number of points with integer coordinates inside OABOAB and b=3+1+0+4b = 3 + 1 + 0 + 4 is the number of points with integer coordinates on the boundary of OABOAB; hence i=47i = 47. The answer is given by the points inside OABOAB plus those inside the segment OAOA, that is i+1=48i + 1 = 48.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.