17th Turkish Mathematical Olympiad

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

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

Now assume that $1<k_1<k_2<\cdots <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}+\cdots +\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^{\prime }=k_i$ and $a_i^{\prime }=2^{-1}{a}_i(\mathrm{mod}K)$ if $k_i$ is odd, and let $k_i^{\prime }=\frac{k_i}{2}$ and $a_i^{\prime }=\frac{a_i}{2}$ if $k_i$ is even. The integers $k_2^{\prime },\dots ,k_n^{\prime }$ and $a_2^{\prime },\dots ,a_n^{\prime }$ satisfy the condition of the problem except that $k_i^{\prime }$ 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^{\prime },k_3^{\prime },k_4^{\prime }\}=\{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^{\prime },k_3^{\prime },k_4^{\prime }\}=\{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^{\prime },k_3^{\prime },k_4^{\prime }\}=\{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^{\prime },k_3^{\prime },k_4^{\prime }\}=\{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$.