Competition problem — Combinatorics

Library / /37 of 82

Combinatorics Difficulty 5.5 AIME, harder Prove it Croatia

We say that two cells of the $10 \times 10$ table are friendly if they have at least one common vertex. Into each cell of the table a positive integer less than or equal to $10$ is written, so that the numbers in friendly cells are relatively prime. Prove that some number appears in the table at least $17$ times.

(St. Petersburg olympiad 2001)

Solution

Let's divide the given table into $25$ smaller squares $2 \times 2$ . In each of these squares there is at most one even number and at most one number divisible by $3$ . Hence, at most $50$ numbers in the table are divisible by $2$ or $3$ . At least $50$ numbers remain, and each of them is equal to $1$ , $5$ or $7$ . By the box principle, at least one of these numbers appears at least $17$ times.

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 and solution reproduced as published; topic and difficulty added by this site.