Here's my solution at any rate. Happy Labor Day! The smallest such $n$ is $n = 5$. Every integer is congruent to one of $0 \pmod 2$, $1 \pmod 3$, $3 \pmod 4$, $5 \pmod 6$, $9 \pmod {12}$. This is easy to check, since one only needs to check this for complete residue classes $\pmod {12}$ since all of $k_i$'s are divisors of $12$, i.e. check only for $N$ in $\{0, 1, 2, \ldots, 11 \}$. So $n \leq 5$. I'll prove that $n = 4$ is impossible (note that this contains the cases $n = 2,3$) Suppose $k_i$'s, $a_i$'s satisfy the conditions of the problem and $n = 4$. We can certainly choose $0 \leq a_i < k_i$. Take any $l > k_n$. Then in $\{0, 1, 2, \ldots, l-1 \}$ the number of integers $\equiv a_i \pmod {k_i}$ is the number of $t$ such that $0 \leq a_i + k_i t \leq l-1$, which is easily seen to be $\left \lfloor \frac{l-1-a_i}{k_i} \right\rfloor $, which is certainly less than $\frac{l}{k_i}$. So $l \leq \sum_{i = 1}^{n} \left \lfloor \frac{l-1-a_i}{k_i} \right\rfloor < \sum_{i = 1}^{n} \frac{l}{k_i}$. Therefore we must have $1 < \sum_{i = 1}^{n} \frac{1}{k_i}$. Since $\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} < 1$, we must have $k_1 = 2$. Since $\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} < 1$, we certainly can't have all of $k_i$ be a power of $2$. So there's an odd prime $p$ dividing one of $k_i$. Suppose $p$ divides $k_i$ but $p$ doesn't divide the other two $k_j$, $k_s$ with $j,s > 1$. Choose $a,b$ such that $a \not \equiv a_i \pmod p$ and $b \not \equiv a_1 \pmod 2$. By Chinese Remainder Theorem, $N \equiv a \pmod 2$ and $N \equiv b \pmod p$ is equivalent to $N \equiv c \pmod {2p}$ for some $c$, for any $a,b$. For $N$ satisfying $N \equiv c \pmod {2p}$, then, we have $N \not \equiv a_i \pmod {k_i}$ and $N \not \equiv a_1 \pmod 2$. So $N \equiv a_j \pmod {k_j}$ or $N \equiv a_s \pmod {k_s}$. Now consider the numbers $c, c+2p, c+4p, c+6p$. These are all $\equiv c \mod {2p}$. So either $k_j,k_s$ both divide $4p$ or one of them divides $2p$. In the latter case, one of $k_j$ or $k_s$ is s $2,p,$ or $2p$. But $p$ doesn't divide them and they're both $> 2$, contradiction. So $k_j$ and $k_s$ must both divide $4p$, but the choices are $2,4,2p,4p$. So they both have to be $4$, but $k_j \not = k_s$, contradiction. Suppose $p$ divides $k_i$ and $k_j$ but $p$ doesn't divide $k_s$, for some $j,s > 1$. As before, we can find $c$ such that $N \equiv c \pmod {2p}$ implies $N \equiv k_s \pmod {k_s}$. This implies that $k_s$ divides both $c - k_s$ and $c + 2p - k_s$, whence divides $2p$, contradiction (since the choices are $2,p$, and $2p$). So $p$ must divide all three $k_2,k_3,k_4$. Suppose $p \geq 5$. Then $\frac{1}{k_1} + \frac{1}{k_2} + \frac{1}{k_3} + \frac{1}{k_4} \leq \frac{1}{2} + \frac{1}{5} + \frac{1}{10} + \frac{1}{15} < 1$, contradiction. So $p = 3$. In other words, the only prime divisors of $k_2,k_3,k_4$ are $2$ or $3$. Now we have $\frac{1}{2} + \frac{1}{6} + \frac{1}{9} + \frac{1}{12} < 1$, so we must have $k_2 = 3$ (otherwise the next possible is $k_2 = 6$, in which case $k_3 \geq 9$ and $k_4 \geq 12$, impossible. Suppose $k_3$ is divisible by $3^2 = 9$. The case $N \equiv a_2 \pmod 3$ accounts for at most $3$ in the residue classes $\pmod 9$. Likewise $N \equiv a_4 \pmod {k_4}$, by Chinese Remainder Theorem, accounts for at most $3$ in residue classes $\pmod 9$. So $a_i \pmod {k_i}$ for $i > 1$ accounts for at most $3 + 3 + 1 < 9$ residue classes $\pmod 9$, so take any $a \pmod 9$ not accounted for, then we must have $N \equiv a \pmod 9$ implies $N \equiv a_1 \pmod 2$, which is impossible as this would imply $2$ divides $9$. So $9$ does not divide $k_3$. For the same reason, $9$ does not divide $k_4$. Now the choices for $k_3$ are $6,9,12,15,\ldots$ and we ruled out $9$. Also $k_3 \geq 12$ is impossible because $\frac{1}{2} + \frac{1}{3} + \frac{1}{12} + \frac{1}{15} < 1$. So $k_3 = 6$. So now $k_4 = 2^v \cdot 3$ for some $v > 1$. Take any $l > 2^v \cdot 3 = k_4$ now. Then $N \equiv a_1 \pmod 2$ and $N \equiv a_2 \pmod 3$ is equivalent to $N \equiv a \pmod 6$ for some $0 \leq a < 6$ by Chinese Remainder Theorem. Therefore the number of times the two congruences $N \equiv a_1 \pmod 2$ and $N \equiv a_2 \pmod 3$ overlap in among $\{0, 1, 2, \ldots, l-1 \}$ is $\left \lfloor \frac{l-1-a}{6} \right \rfloor \geq \frac{l-12}{6}$. Therefore, $l \leq \frac{l}{2} + \frac{l}{3} + \frac{l}{6} + \frac{l}{2^v \cdot 3} - \frac{l - 12}{6}$, or $1 \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{2^v \cdot 3} - \frac{\frac{l-12}{l}}{6}$. Taking $l \to \infty$, we have $1 \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{2^v \cdot 3} \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{12} < 1$, contradiction. So $n \geq 5$, and done. Remark. I was a little more detailed than usual. Also, one can save a lot of those Chinese Remainder Theorem arguments by being a little more careful with choice of $l$ and the approximation for the coverage of congruence in $\{0, 1, 2, \ldots, l-1 \}$ but a little more work during labor day isn't so bad

Here is the official solution. 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 \leq 4$ is not possible. Let $1<k_1\leq k_2 \leq ... \leq k_n$ and $a_1,a_2,...,a_n$ be integers, and let $K= lcm(k_1,k_2,...,k_n).$ Since at most $\frac{K}{k_1}+\frac{K}{k_2}+...+\frac{K}{k_n}$ integers from $1$ to $K$ can satisfy at least one of the congruences $x \equiv a_i \pmod{k_i}$ for $1 \leq i \leq n,$ we must have $\frac{1}{k_1}+\frac{1}{k_2}+...+\frac{1}{k_n} \geq 1$ if every integer satisfies at least one of these congruences. Now assume that $1<k_1<k_2<...<k_n$ and $a_1,a_2,...,a_n$ satisfy the condition of the problem and that $n \leq 4$ has the smallest possible value. If $k_1 \geq 3,$ then $\frac{1}{k_1}+\frac{1}{k_2}+...+\frac{1}{k_n} \leq \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 \leq i \leq n,$ let ${k_i}'=k_i$ and ${a_i}' \equiv \frac{a_i}{2} \pmod {k_i}$ 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_1}',{k_2}',...,{k_n}'$ and ${a_1}',{a_2}',...,{a_n}'$ satsify 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\}.$ $i)$ If $k$ is odd, then $\{{k_2}',{k_3}',{k_4}'\}=\{2m+1,2m+1,k\}$ and $\frac{2}{2m+1}+\frac{1}{k} \geq 1.$ Since $\frac{2}{2m+1}+\frac{1}{k} \leq \frac{2}{3}+\frac{1}{5}=\frac{13}{15}<1,$ this is not possible. $ii)$ If $k$ is even, then $\{{k_2}',{k_3}',{k_4}'\}=\left\{2m+1,2m+1,\frac{k}{2}\right\}$ and $\frac{2}{2m+1}+\frac{2}{k} \geq 1.$ If $2m+1 \geq 5$ or $2m+1=3$ and $k \geq 8,$ we get contradictions because $\frac{2}{5}+\frac{2}{4}=\frac{9}{10}<1$ 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 congrunces class modulo $3$ cannot be all even or all odd, this also leads to a contradiction.

Note that there are other congruences that work, for example $1 \pmod 2$ $0 \pmod 3$ $0 \pmod 4$ $2 \pmod 6$ $10 \pmod {12}$ Finding these is easy, as one need only need to knock out all integers ${\pmod l}$ with $a_i \pmod {k_i}$ and all of $k_i$ dividing $l$, and it's natural to try to find smallest $l$ with many factors (relative to itself), for example numbers whose sum of proper divisors is greater than or equal to itself. The first two such numbers are $6$ and $12$, and you can try that three congruences $a_1 \pmod 2$, $a_2 \pmod 3$, $a_3 \pmod 6$ cannot knock out all $\pmod 6$, so you try $\pmod {12}$ and the first set of congruences $a_1 \pmod 2$, $a_2 \pmod 3$, $a_3 \pmod 4$, $a_4 \pmod 6$, and $a_5 \pmod {12}$ you'll try will work

hochs wrote: Here's my solution at any rate. Happy Labor Day! The smallest such $n$ is $n = 5$. Every integer is congruent to one of $0 \pmod 2$, $1 \pmod 3$, $3 \pmod 4$, $5 \pmod 6$, $9 \pmod {12}$. This is easy to check, since one only needs to check this for complete residue classes $\pmod {12}$ since all of $k_i$'s are divisors of $12$, i.e. check only for $N$ in $\{0, 1, 2, \ldots, 11 \}$. So $n \leq 5$. I'll prove that $n = 4$ is impossible (note that this contains the cases $n = 2,3$) Suppose $k_i$'s, $a_i$'s satisfy the conditions of the problem and $n = 4$. We can certainly choose $0 \leq a_i < k_i$. Take any $l > k_n$. Then in $\{0, 1, 2, \ldots, l-1 \}$ the number of integers $\equiv a_i \pmod {k_i}$ is the number of $t$ such that $0 \leq a_i + k_i t \leq l-1$, which is easily seen to be $\left \lfloor \frac{l-1-a_i}{k_i} \right\rfloor $, which is certainly less than $\frac{l}{k_i}$. So $l \leq \sum_{i = 1}^{n} \left \lfloor \frac{l-1-a_i}{k_i} \right\rfloor < \sum_{i = 1}^{n} \frac{l}{k_i}$. Therefore we must have $1 < \sum_{i = 1}^{n} \frac{1}{k_i}$. Since $\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} < 1$, we must have $k_1 = 2$. Since $\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} < 1$, we certainly can't have all of $k_i$ be a power of $2$. So there's an odd prime $p$ dividing one of $k_i$. Suppose $p$ divides $k_i$ but $p$ doesn't divide the other two $k_j$, $k_s$ with $j,s > 1$. Choose $a,b$ such that $a \not \equiv a_i \pmod p$ and $b \not \equiv a_1 \pmod 2$. By Chinese Remainder Theorem, $N \equiv a \pmod 2$ and $N \equiv b \pmod p$ is equivalent to $N \equiv c \pmod {2p}$ for some $c$, for any $a,b$. For $N$ satisfying $N \equiv c \pmod {2p}$, then, we have $N \not \equiv a_i \pmod {k_i}$ and $N \not \equiv a_1 \pmod 2$. So $N \equiv a_j \pmod {k_j}$ or $N \equiv a_s \pmod {k_s}$. Now consider the numbers $c, c+2p, c+4p, c+6p$. These are all $\equiv c \mod {2p}$. So either $k_j,k_s$ both divide $4p$ or one of them divides $2p$. In the latter case, one of $k_j$ or $k_s$ is s $2,p,$ or $2p$. But $p$ doesn't divide them and they're both $> 2$, contradiction. So $k_j$ and $k_s$ must both divide $4p$, but the choices are $2,4,2p,4p$. So they both have to be $4$, but $k_j \not = k_s$, contradiction. Suppose $p$ divides $k_i$ and $k_j$ but $p$ doesn't divide $k_s$, for some $j,s > 1$. As before, we can find $c$ such that $N \equiv c \pmod {2p}$ implies $N \equiv k_s \pmod {k_s}$. This implies that $k_s$ divides both $c - k_s$ and $c + 2p - k_s$, whence divides $2p$, contradiction (since the choices are $2,p$, and $2p$). So $p$ must divide all three $k_2,k_3,k_4$. Suppose $p \geq 5$. Then $\frac{1}{k_1} + \frac{1}{k_2} + \frac{1}{k_3} + \frac{1}{k_4} \leq \frac{1}{2} + \frac{1}{5} + \frac{1}{10} + \frac{1}{15} < 1$, contradiction. So $p = 3$. In other words, the only prime divisors of $k_2,k_3,k_4$ are $2$ or $3$. Now we have $\frac{1}{2} + \frac{1}{6} + \frac{1}{9} + \frac{1}{12} < 1$, so we must have $k_2 = 3$ (otherwise the next possible is $k_2 = 6$, in which case $k_3 \geq 9$ and $k_4 \geq 12$, impossible. Suppose $k_3$ is divisible by $3^2 = 9$. The case $N \equiv a_2 \pmod 3$ accounts for at most $3$ in the residue classes $\pmod 9$. Likewise $N \equiv a_4 \pmod {k_4}$, by Chinese Remainder Theorem, accounts for at most $3$ in residue classes $\pmod 9$. So $a_i \pmod {k_i}$ for $i > 1$ accounts for at most $3 + 3 + 1 < 9$ residue classes $\pmod 9$, so take any $a \pmod 9$ not accounted for, then we must have $N \equiv a \pmod 9$ implies $N \equiv a_1 \pmod 2$, which is impossible as this would imply $2$ divides $9$. So $9$ does not divide $k_3$. For the same reason, $9$ does not divide $k_4$. Now the choices for $k_3$ are $6,9,12,15,\ldots$ and we ruled out $9$. Also $k_3 \geq 12$ is impossible because $\frac{1}{2} + \frac{1}{3} + \frac{1}{12} + \frac{1}{15} < 1$. So $k_3 = 6$. So now $k_4 = 2^v \cdot 3$ for some $v > 1$. Take any $l > 2^v \cdot 3 = k_4$ now. Then $N \equiv a_1 \pmod 2$ and $N \equiv a_2 \pmod 3$ is equivalent to $N \equiv a \pmod 6$ for some $0 \leq a < 6$ by Chinese Remainder Theorem. Therefore the number of times the two congruences $N \equiv a_1 \pmod 2$ and $N \equiv a_2 \pmod 3$ overlap in among $\{0, 1, 2, \ldots, l-1 \}$ is $\left \lfloor \frac{l-1-a}{6} \right \rfloor \geq \frac{l-12}{6}$. Therefore, $l \leq \frac{l}{2} + \frac{l}{3} + \frac{l}{6} + \frac{l}{2^v \cdot 3} - \frac{l - 12}{6}$, or $1 \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{2^v \cdot 3} - \frac{\frac{l-12}{l}}{6}$. Taking $l \to \infty$, we have $1 \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{2^v \cdot 3} \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{12} < 1$, contradiction. So $n \geq 5$, and done. Remark. I was a little more detailed than usual. Also, one can save a lot of those Chinese Remainder Theorem arguments by being a little more careful with choice of $l$ and the approximation for the coverage of congruence in $\{0, 1, 2, \ldots, l-1 \}$ but a little more work during labor day isn't so bad After we found $k_3 = 6$ could we directly say that $k_4$ has to divide $6$ ? Because the case $N \equiv a_2 \pmod 3$ accounts for at most $2$ in the residue classes $\pmod 6$ and $N \equiv a_1 \pmod 2$ accounts for at most $3$ in the residue classes $\pmod6$ . Note that, one of them must be equivalent. Obviously $N \equiv a_3 \pmod 6$ accounts for exactly one residue in $\pmod 6$ . So $a_i \pmod {k_i}$ accounts for at most $2 + 3 - 1 + 1 < 6$ residue classes $\pmod 6$ . This implies that $k_4$ divides $6$ ,like we just did, which is impossible.