28th Hellenic Mathematical Olympiad

Figure 2

A point $M(k,l)$ will belong in the interior of the line segment $O{A}_i$, if and only if $\overrightarrow{OM}$ and $\overrightarrow{O{A}_i}$ have the same slope (with $k,l$ integers and $0<k\le 40$), that is $$\frac{i}{40}=\frac{l}{k}(\text{with }k,l\text{ integers and }0<k\le 40).$$ In order the line segment $O{A}_i$ be "good" it is enough and sufficient the fraction $\frac{i}{40}$ to be reducible (then we have fraction $\frac{l}{k}$ with integer terms equivalent to $\frac{i}{40}$ and its terms give the coordinates of the "good" point $M(k,l)$). Hence, if $(40,i)>1$, then the line segment $O{A}_i$ is "good" and we have $(40,i)-1$ "good" points at the segment $O{A}_i$. To the point $A_2(40,2)$ corresponds the "good" segment $O{A}_2$, which contains the good point $(20,1)$. To point $A_4(40,4)$ corresponds the "good" segment $O{A}_4$, which contain the "good" points $(10,1)$, $(20,2)$, $(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. $\varphi$. It is known that the number of positive integers lower or equal to $n$ and not relatively prime to $n$ is $n-\varphi (n)$. Since $40=5\cdot 2^3$, we have $$\varphi (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-\varphi (40)=24$.