Solution
Visible From the Origin
Show the problem again
Trees stand at every lattice point $(x, y)$ with $1 \le x \le 10$ and $1 \le y \le 10$. Trees are thin, but a tree hides any tree directly behind it on the same ray from the origin. A tree at $(x, y)$ is visible from $(0, 0)$ if no other tree lies on the segment between them. How many of the 100 trees are visible? Give an integer.
Worked solution
The answer is 63. The tree at $(x, y)$ is blocked exactly when $g = \gcd(x, y) > 1$, since then $(x/g, y/g)$ is a tree on the segment. So we count coprime pairs in the 10 × 10 square. By symmetry, count pairs with $x < y$ plus the diagonal. For each $y$ from 2 to 10 there are $\varphi(y)$ values $x < y$ coprime to $y$: $1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31$. Doubling gives 62, and the diagonal adds only (1, 1). Total: 63. (For large squares the visible fraction tends to $6/\pi^2 \approx 0.61$.)
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.