(a) $n$ is a natural number. $d_1,\dots,d_n,r_1,\dots ,r_n$ are natural numbers such that for each $i,j$ that $1\leq i < j \leq n$ we have $(d_i,d_j)=1$ and $d_i\geq 2$. Prove that there exist an $x$ such that (i) $1 \leq x \leq 3^n$ (ii)For each $1 \leq i \leq n$ \[x \overset{d_i}{\not{\equiv}} r_i\] (b) For each $\epsilon >0$ prove that there exists natural $N$ such that for each $n>N$ and each $d_1,\dots,d_n,r_1,\dots ,r_n$ satisfying the conditions above there exists an $x$ satisfying (ii) such that $1\leq x \leq (2+\epsilon )^n$. Time allowed for this exam was 75 minutes.
Problem
Source: Iran 3rd round 2014 - final exam problem 3
Tags: number theory unsolved, number theory
09.05.2018 21:50
Bump, any ideas for the first part ? I’m trying with CRT + induction . Maybe someone can continue ?
11.05.2018 07:30
Note that, for all positive integers $d$ and $r$, among any $n$ consecutive integers, there're more than $\frac{n}{d}-1$ and less than $\frac{n}{d}+1$ number that congruence to $r$ modulo $d$. So, the number of positive integer $x$ less than $3^n$ that $x\not\equiv r_i \pmod{d_i}$ for all $i=1,2,\dotsc ,n$ is at least $$3^n-\sum_{i=1}^{n}{\left( \frac{3^n}{d_i}+1\right) }+\sum_{1\leq i<j\leq n}{\left( \frac{3^n}{d_id_j}-1\right) }-\cdots +(-1)^n\left( \frac{3^n}{d_1d_2\cdots d_n} +(-1)^{n+1}\right) =3^n\prod_{i=1}^{n}{(1-\frac{1}{d_i})}-(2^n-1).$$Note that $\prod_{i=1}^{n}{(1-\frac{1}{d_i})} \geqslant \prod_{i=1}^{n}{(1-\frac{1}{i+1})}\geqslant \frac{1}{n+1}$. Hence, $3^n\prod_{i=1}^{n}{(1-\frac{1}{d_i})}-(2^n-1)\geqslant \frac{3^n}{n+1}-(2^n-1) >0$ while the last inequality is true for all $n\neq 2,3$.
For the second part, simply note that for suff large $n$, the inequality $\frac{ \lfloor (2+\epsilon )^n\rfloor}{n+1}-(2^n-1)$ holds, done.
08.07.2019 23:21
It is a well-known problem of erdos that any $k$ arithmetic progressions that contains at least $2^k$ consecutive integers is a covering system so we are done.