Iranian Mathematical Olympiad

a) Without loss of generality, we may suppose that $1 < d_1 < \dots < d_n$. First, suppose that $d_1 > 2$. For each subset $I = \{i_1 < \dots < i_k\} \subseteq \{1, 2, \dots, n\}$, we define $d_I$ to be equal to the product $d_{i_1} d_{i_2} \dots d_{i_k}$. By the Chinese Remainder Theorem, we know that the modular equalities
$$x \equiv r_{i_1} \pmod{d_{i_1}}, \dots, x \equiv r_{i_k} \pmod{d_{i_k}} \quad (*)$$
have a unique solution modulo $d_I$. Let $r_I$ be one of its solutions (If $I = \emptyset$ there is no equation and so all integers are solutions. In this case, we set $r_I = 1$). So $x \equiv r_I \pmod{d_I}$ is equivalent to the system $(*)$.

Now suppose that $M$ is an arbitrary integer. According to the Inclusion-Exclusion Principle, the number of solutions of modular inequalities
$$x \not\equiv r_1 \pmod{d_1}, \dots, x \not\equiv r_n \pmod{d_n}$$
which are greater than $M$ is
$$\sum_{I \subseteq \{1, \dots, n\}} (-1)^{|I|} |\{1 \le x \le M \mid x \equiv r_I \pmod{d_I}\}|.$$
It is easy to see that the number of solutions of each modular equality like $x \equiv r \pmod{d}$ in $[1, M]$ is $\lfloor \frac{M}{d} \rfloor$ or $\lceil \frac{M}{d} \rceil$. In each case, the difference of the number of solutions and $\frac{M}{d}$ is at most one, so the number of solutions is greater than
$$\left( \sum_{I \subseteq \{1, \dots, n\}} (-1)^{|I|} \frac{M}{d_I} \right) - 2^n = M \left( 1 - \frac{1}{d_1} - \dots - \frac{1}{d_n} + \frac{1}{d_1 d_2} + \dots \right) - 2^n \\ = M \left(1 - \frac{1}{d_1}\right) \dots \left(1 - \frac{1}{d_n}\right) - 2^n.$$

Now, if $M = 3^n$ and $d_i \ge 3$ for all $i$, this number is at least
$$3^n\left(1 - \frac{1}{3}\right)^n - 2^n = 0.$$
And so in this case the number of solutions of inequalities is not zero. For the case $d_1 = 2$, parity of $x$ is determined by the parity of $r_1$. Thus, we can use one of substitutions $x = 2y$ or $x = 2y - 1$. This substitution changes the other inequalities to some new ones in terms of $y$
$$y \not\equiv s_2 \pmod{d_2}, \dots, y \not\equiv s_n \pmod{d_n}$$
Since $3 \le d_2 < \dots < d_n$, these inequalities have a solution $y_0 \le 3^{n-1}$. Hence, we can find a solution for the main inequalities $(x)$ not greater than $2 \times 3^{n-1} < 3^n$. So the proof is complete.

b) Similar to the previous part, we assume that $d_1 < d_2 < \dots < d_n$. Therefore, for each $i$, we have $d_i \ge i$. Furthermore, suppose that $\epsilon > 0$ has been given. We choose a real number $a \in (\frac{2}{2+\epsilon}, 1)$. Obviously, there is some $N_1$ such that $1 - \frac{1}{N_1} > a$. On the other hand, since $\frac{(2+\epsilon)a}{2} > 1$, there is $N_2$ such that
$$\left(\frac{(2 + \epsilon)a}{2}\right)^{N_2} > 2^{N_1}.$$
Now we set $N = N_1 + N_2$. We will show that for each $n > N$ the number of solutions of the system of modular inequalities is at most $(2 + \epsilon)^n$. According to part (a), we know that the number of solutions of these inequalities in $[1, (2 + \epsilon)^n]$ is more than
$$(2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) - 2^n.$$
But for $n > N$ we have
$$\begin{aligned} (2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) &\ge (2 + \epsilon)^n \left(1 - \frac{1}{2}\right) \cdots \left(1 - \frac{1}{n+1}\right) \\ &\ge (2 + \epsilon)^n \left(1 - \frac{1}{2}\right)^{N_1} \left(1 - \frac{1}{N_1}\right)^{n-N_1} \\ &\ge (2 + \epsilon)^n 2^{-N_1} a^{n-N_1} \\ &\ge (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^{n-N_1} \left(\frac{(2+\epsilon)a}{2}\right)^{n-N_1}. \end{aligned}$$
Note that $\frac{2}{2+\epsilon} < 1$, $\frac{(2+\epsilon)a}{2} > 1$ and $n - N_1 > N_2$. Therefore,
$$\begin{aligned} & (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^{n-N_1} \left(\frac{(2+\epsilon)a}{2}\right)^{n-N_1} > (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^n \left(\frac{(2+\epsilon)a}{2}\right)^{N_2} \\ & > (2 + \epsilon)^n 2^{-N_1} \left(\frac{2}{2+\epsilon}\right)^n 2^{N_1} \\ & = 2^n. \end{aligned}$$
And finally, we get
$$(2 + \epsilon)^n \left(1 - \frac{1}{d_1}\right) \cdots \left(1 - \frac{1}{d_n}\right) - 2^n > 0$$