Turkish Mathematical Olympiad

Every integer $N$ satisfies at least one of the congruences $N \equiv 0 \pmod{2}$, $N \equiv 1 \pmod{3}$, $N \equiv 3 \pmod{4}$, $N \equiv 5 \pmod{6}$, $N \equiv 9 \pmod{12}$. Therefore $n$ can be $5$. We will show that $n \le 4$ is not possible.

Let $1 < k_1 \le k_2 \le \dots \le k_n$ and $a_1, a_2, \dots, a_n$ be integers, and let $K = \operatorname{lcm}(k_1, k_2, \dots, k_n)$. Since at most $\frac{K}{k_1} + \frac{K}{k_2} + \dots + \frac{K}{k_n}$ integers from $1$ to $K$ can satisfy at least one of the congruences $x \equiv a_i \pmod{K}$ for $1 \le i \le n$, we must have $\frac{1}{k_1} + \frac{1}{k_2} + \dots + \frac{1}{k_n} \ge 1$ if every integer satisfies at least one of these congruences.

Now assume that $1 < k_1 < k_2 < \dots < k_n$ and $a_1, a_2, \dots, a_n$ satisfy the condition of the problem and that $n \le 4$ has the smallest possible value. If $k_1 = 3$, then $\frac{1}{k_1} + \frac{1}{k_2} + \dots + \frac{1}{k_n} \le \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} = \frac{19}{20} < 1$. Therefore $k_1 = 2$.

Without loss of generality we may assume that $a_1 = 1$. For $2 \le i \le n$, let $k_i' = k_i$ and $a_i' = 2^{-1} a_i \pmod{K}$ if $k_i$ is odd, and let $k_i' = \frac{k_i}{2}$ and $a_i' = \frac{a_i}{2}$ if $k_i$ is even. The integers $k_2', \dots, k_n'$ and $a_2', \dots, a_n'$ satisfy the condition of the problem except that $k_i'$ might not be distinct. Therefore by the minimality of $n$, we must have $n = 4$ and $\{k_2, k_3, k_4\} = \{2m+1, 4m+2, k\}$.

* If $k$ is odd, then $\{k_2', k_3', k_4'\} = \{2m+1, 2m+1, k\}$ and $\frac{2}{2m+1} + \frac{1}{k} \ge 1$. Since $\frac{2}{2m+1} + \frac{1}{k} \le \frac{2}{3} + \frac{1}{5} = \frac{13}{15} < 1$, this is not possible.

$$\frac{2}{5} + \frac{2}{4} = \frac{9}{10} < 1 \text{ and } \frac{2}{3} + \frac{2}{8} = \frac{11}{12} < 1. \text{ The only remaining case is } 2m+1 = 3 \text{ and } k=4. \text{ This gives } \{k'_2, k'_3, k'_4\} = \{3, 3, 2\}. \text{ Since the integers in a congruence class modulo 3 cannot be all even or all odd, this also leads to a contradiction.}$$

* If $k$ is even, then $\{k_2', k_3', k_4'\} = \{2m+1, 2m+1, \frac{k}{2}\}$ and $\frac{2}{2m+1} + \frac{2}{k} \ge 1$. If $2m+1 \ge 5$ or $2m+1=3$ and $k \ge 8$, we get contradictions because
$$\frac{2}{5} + \frac{2}{4} = \frac{9}{10} < 1 \text{ and } \frac{2}{3} + \frac{2}{8} = \frac{11}{12} < 1.$$
The only remaining case is $2m+1 = 3$ and $k=4$. This gives $\{k'_2, k'_3, k'_4\} = \{3, 3, 2\}$. Since the integers in a congruence class modulo $3$ cannot be all even or all odd, this also leads to a contradiction.

Therefore, the smallest possible value of $n$ is $5$.