Olympiad Maths Prep

Library / /3 of 5

Number theory Difficulty 6.9 National olympiad Prove it Greece

In the Cartesian plane OxyOxy we consider the points A1(40,1)A_1(40,1), A2(40,2)A_2(40,2), ..., A40(40,40)A_{40}(40,40), as well as the line segments OA1,OA2,...,OA40OA_1, OA_2, ..., OA_{40}. A point of the Cartesian plane will be called "good" if its coordinates are integers and lies in the interior of a line segment OAiOA_i, i=1,2,3,...,40i = 1, 2, 3, ..., 40. Also a line segment from OA1,OA2,...,OA40OA_1, OA_2, ..., OA_{40}, will be called "good" if it contains at least one "good" point. Determine the number of "good" points and the number of "good" segments.

Solution

Figure 1
Figure 2

A point M(k,l)M(k,l) will belong in the interior of the line segment OAiOA_i, if and only if OM\overrightarrow{OM} and OAi\overrightarrow{OA_i} have the same slope (with k,lk,l integers and 0<k400 < k \le 40), that is
i40=lk(with k,l integers and 0<k40). \frac{i}{40} = \frac{l}{k} \quad (\text{with } k,l \text{ integers and } 0 < k \le 40).
In order the line segment OAiOA_i be "good" it is enough and sufficient the fraction i40\frac{i}{40} to be reducible (then we have fraction lk\frac{l}{k} with integer terms equivalent to i40\frac{i}{40} and its terms give the coordinates of the "good" point M(k,l)M(k,l)).
Hence, if (40,i)>1(40,i) > 1, then the line segment OAiOA_i is "good" and we have (40,i)1(40,i)-1 "good" points at the segment OAiOA_i. To the point A2(40,2)A_2(40,2) corresponds the "good" segment OA2OA_2, which contains the good point (20,1)(20,1). To point A4(40,4)A_4(40,4) corresponds the "good" segment OA4OA_4, which contain the "good" points (10,1)(10,1), (20,2)(20,2), (30,3)(30,3). Working in this way we finally find 24 "good" segments and 140 "good" points.

An easy solution can be given by using the Euler function. ϕ\phi. It is known that the number of positive integers lower or equal to nn and not relatively prime to nn is nϕ(n)n-\phi(n). Since 40=52340 = 5 \cdot 2^3, we have
ϕ(40)=40(112)(115)=401425=16. \phi(40) = 40 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{5}\right) = 40 \frac{14}{25} = 16.
Hence the number of good segments is 40ϕ(40)=2440 - \phi(40) = 24.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.