(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
omarius
09.05.2018 21:50
Bump, any ideas for the first part ? I’m trying with CRT + induction . Maybe someone can continue ?
ThE-dArK-lOrD
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$.
If $d_1>2$, we get $\prod_{i=1}^{n}{(1-\frac{1}{d_i})} \geqslant \prod_{i=1}^{n}{(1-\frac{1}{i+2})}\geqslant \frac{2}{n+2}$.
Hence, $3^n\prod_{i=1}^{n}{(1-\frac{1}{d_i})}-(2^n-1)\geqslant \frac{2\times 3^n}{n+2}-(2^n-1) >0$ for all $n\in \{ 2,3\}$.
So, we're done in the case that $d_1>2$. In case that $d_1=2$, we've, again, boring casework.If $d_2>3$, we get $\prod_{i=1}^{n}{(1-\frac{1}{d_i})} \geqslant \frac{1}{2}\prod_{i=2}^{n}{(1-\frac{1}{i+2})}=\frac{3}{2(n+2)}$.
Hence, $3^n\prod_{i=1}^{n}{(1-\frac{1}{d_i})}-(2^n-1)\geqslant \frac{3^{n+1}}{2(n+2)}-(2^n-1) >0$ for all $n\in \{ 2,3\}$.
So, we're done in the case that $d_2>3$. In case that $d_2=3$, we have
$n=2$. We have $3^n>d_1d_2\cdots d_n$, i.e., we've complete residue modulo $d_1d_2\cdots d_n$, done.
$n=3$. We get $d_3>4$, so $\prod_{i=1}^{n}{(1-\frac{1}{d_i})} \geqslant (1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=\frac{4}{15}$.
Hence, $3^n\prod_{i=1}^{n}{(1-\frac{1}{d_i})}-(2^n-1)\geqslant \frac{4\times 27}{15}-7>0$, done.
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.
Taha1381
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.