First we note that all these numbers are primes

rahman wrote: First we note that all these numbers are primes then W,L,O,G we asume that $m_{2013}> m_{2012}> ...> m_{1}$ note that $\left | A_{i} \right |=m_{i}-1$ Already in your first three statements there are two errors...

This is a nice problem, and it's been a while, so I guess:

This ended up being slightly easier than I expected. That may be due to the fact though that I just solved this China TST prob (on my blog) (here's the actual problem page) a few days ago. It would be interesting if Victor could mention how he thought up this problem; I would be somewhat surprised if it wasn't from that problem. Anyways, here's the solution. Work $\pmod{P}$, where $P = m_1m_2\cdots m_n$. ($n = 2013$) Denote the set $S_i = \{0, 1, 2, \cdots , m_i-1\}$. So let $t_i$ be the solution for $x$ to the set of congruences $x \equiv 0 \pmod{m_j}$ for $j \not = i$ and $x \equiv 1 \pmod{m_i}$. Now the "Lagrange Interpolation CRT" is to note that the solution for $x$ to the congruence system $x \equiv x_i \pmod{m_i}$ is actually just $\sum_{i=1}^n{x_it_i}$. Now we construct sets $B_i$ $\pmod {m_i}$, so that the set $\{B_i- B_i\} \subset S_i/A_i$ (the set of all differences of elements in $B_i$), and $\vert{B_i}\vert \ge \frac{m_i}{2\vert{A_i}\vert +1}$. This is equivalent to $B_i$, $A_i$ being disjoint. The construction is simple. Assume that the best value of $\vert{B_i}\vert$ that we can achieve is less than $\frac{m_i}{2\vert{A_i}\vert +1}$. Now we consider whether we can add another element. Note that at most $2\vert{A_i}\vert \cdot \vert {B_i}\vert +\vert {B_i} \vert < (2\vert{A_i}\vert+1) \cdot \frac{m_i}{2\vert{A_i}\vert +1} = m_i$ elements are not allowed to be picked. So we can pick some element to add to our set. Now consider the set $S$ of all the (distinct) numbers $\pmod{P}$ $\sum_{i=1}^n{b_it_i}$, where $b_i \in B_i$ for all $i$. Since we have $$\frac{m_1m_2\cdots m_n}{\left( 2\left\lvert A_1\right\rvert+1\right)\left( 2\left\lvert A_2\right\rvert+1\right)\cdots\left( 2\left\lvert A_{n}\right\rvert+1\right)}$$ in our set $S$, two differ by at most $${\left( 2\left\lvert A_1\right\rvert+1\right)\left( 2\left\lvert A_2\right\rvert+1\right)\cdots\left( 2\left\lvert A_{n}\right\rvert+1\right)}$$ , so if we can finish by taking their difference.

mathocean97 wrote: It would be interesting if Victor could mention how he thought up this problem; I would be somewhat surprised if it wasn't from that problem. I roughly used the $|A_i| = 2$ case as a lemma for the following problem: Quote: Given $c>0$, prove that $n^2+1$ infinitely often has all prime divisors at least $c\log{n}$. I think I wrote more about this in the official solutions (in some of the comments), but I was indeed influenced at least a bit by that China TST problem---otherwise I probably wouldn't have forgotten about Solutions 2 and 3 the first time around.

Here is a solution for the bound $(|A_1| + 1) \cdots (|A_{2013}| + 1)$. The idea is the same as one in a solution in PftB. Quote: Let $m_1, \dots, m_{2013} > 1$ be 2013 pairwise relatively prime positive integers and $A_1, \dots, A_{2013}$ be 2013 sets with $A_i \subseteq \{1, \dots, m_i-1\}$ for all $i$. Prove that there is a positive integer $N$ such that $$N \le (|A_1| + 1) \cdots (|A_{2013}| + 1)$$ and for each $i$, there does not exist $a \in A_i$ such that $m_i$ divides $N-a$. For convenience define $s_k = |A_k|$. For each $n$, define $$x_n = \prod_{k = 1}^{2013} \prod_{a \in A_k} (1 - e^{2\pi i(n - a)/m_k}).$$ Then $x_n \neq 0$ iff $n$ is valid. When expanded, the product $\prod_{a \in A_k} (1 - e^{2\pi i(n - a)/m_k})$ takes the form $$c_0 + c_1 \varepsilon_k^n + \dots + c_{s_k} (\varepsilon_k^{s_k})^n,$$ where $c_0, \dots, c_{s_k}$ are constants and $\varepsilon_k = e^{2\pi i/m_k}$. In particular, it has $s_k + 1$ terms. Thus, upon expansion, $x_n$ is the sum of $s \stackrel{\text{def}}{=} (s_1 + 1) \cdots (s_{2013} + 1)$ terms of the form $$\lambda (\varepsilon_1^{f_1} \cdots \varepsilon_{2013}^{f_{2013}})^n,$$ where $\lambda$ is a constant and $f_1, \dots, f_{2013}$ are nonnegative integers. This means $\{x_n\}$ is a linear recurrence of order $s$. If none of $1, \dots, s$ are valid then $x_1 = \dots = x_s = 0$, which forces all $x_k = 0$; i.e. all $k$ invalid. But this is a contradiction since any multiple of $m_1 \cdots m_{2013}$ is valid.

For each $i$, define $t_i$ to be the unique residue modulo $\displaystyle\prod_{i=1}^{2013}m_i$ such that $t_i\equiv 1\pmod{m_i},t_i\equiv 0\pmod{m_j}\forall j\ne i$. Let $B_i$ be the largest subset of $\mathbb{Z}/m_i$ such that $(B_i-B_i)\cap A_i=\emptyset$. Then, consider the numbers $$\sum_{i=1}^{2013}b_it_i$$ where $b_i\in B_i$ for all $i$. It is clear that the difference of any two of these numbers' residue modulo $m_i$ is not in $A_i$ for any $i$, hence it suffices to show that there are at least $$\frac{\prod_{i=1}^{2013}m_i}{\prod_{i=1}^{2013}(2|A_i|+1)}$$ of these numbers by the Pigeonhole Principle. Thus, it suffices to show the inequality $$|B_i| \ge \frac{m_i}{2|A_i|+1}$$ for any $i$. Now, we use a greedy algorithm to construct such a set $B_i$. We start with the set $B_i = \{0\}$. Suppose that at some point $B_i$ has $k$ nonzero elements, $r_1,\dots , r_k$. Any new element $x$ added to $B_i$ must satisfy the following constraints $$x,-x\not\in A_i, \forall 1\le j\le k, x-r_k,-x+r_k\not\in A_i.$$ This constitutes $2k+2$ constraints. Thus, any random choice of $x$ chosen from the remaining $m_i-k-1$ choices will have an expected $$\frac{(2k+2)\cdot |A_i|}{m_i-1}$$ violations. Thus, there will exist some working choice of $x$ as long as $|B_i|\cdot 2|A_i| = (k+1)\cdot 2|A_i| < m_i-1$. Hence, we have that $$|B_i| \ge \frac{m_i-1}{2|A_i|} = \frac{m_i}{2|A_i|} \cdot \frac{m_i-1}{m_i}.$$ Note that as long as $$\frac{2|A_i|}{2|A_i|+1} \le \frac{m_i-1}{m_i},$$ that is, $2|A_i| \le m-1$, this implies the desired result. Otherwise, we have $2|A_i| > m_i-1$, so the result trivially holds because we have $|B_i| \ge 1$. Thus, we have shown the desired inequality and thus proven the full result.

. We will prove a slightly stronger statement: if $n$ is a positive integer, and $m_1, \ldots, m_n, m$ are pairwise relatively prime, and $A_i$ is a proper subset of the residues mod $m_i$ for all $1 \le i \le n$, then any arithmetic progression with common difference $m$ and at least $$N = \prod_{i=1}^{n} (2|A_i|+1)$$ terms contains a term $x$ such that for all $1 \le i \le n$, there does not exist $a \in A_i$ such that $x \equiv a \pmod{m_i}$. We prove this by induction on $n$, base case $n=1$ trivial. Suppose the hypothesis holds for $n-1$, we will prove it for $n$. Case 1: There exists $i$ such that $2|A_i| + 1 \ge m_i$, WLOG $i = n$ by reordering. Pick some mod-$m_n$ residue $y$ not in $A_n$. Because $\gcd(m_n, m) = 1$, the given arithmetic progression contains a subprogression where every term is congruent to $y \pmod{m_n}$ and with at least $$\left\lfloor\frac{\prod_{i=1}^{n}(2|A_i|+1)}{m_n}\right\rfloor \ge \left\lfloor\frac{\prod_{i=1}^{n}(2|A_i|+1)}{2|A_n|+1}\right\rfloor = \prod_{i=1}^{n-1}(2|A_i|+1)$$ terms. Now simply apply the induction hypothesis on $m_1, \ldots, m_{n-1}$, and $m$ replaced with $mm_n$. Case 2: For all $i$, $m_i > 2|A_i| + 1$. Take any $S \subseteq \{1, 2, \ldots, n\}$, and for every $i \in S$, pick some $y_i \in A_i$. Clearly the number of terms in the arithmetic progression which are congruent to $y_i$ mod $m_i$ for all $i \in S$ deviates from the quantity $\frac{N}{\prod_{i \in S} m_i}$ by less than 1. Then using PIE, the number of terms $x$ in the arithmetic progression satisfying $x \not \equiv a \pmod{m_i}$ for any $i$, $a \in A_i$ deviates from $$N - \frac{N|A_1|}{m_1} - \ldots - \frac{N|A_n|}{m_n} + \frac{N|A_1||A_2|}{m_1m_2} + \ldots - \ldots \ldots \pm \frac{N|A_1||A_2|\cdots |A_n|}{m_1m_2\cdots m_n}$$ $$= N\prod_{i=1}^{n}\left(1 - \frac{|A_i|}{m_i}\right)$$ by less than $$1 + |A_1| + \ldots + |A_n| + |A_1||A_2| + \ldots + \ldots + |A_1||A_2|\cdots|A_n|$$ $$= \prod_{i=1}^{n}(|A_i|+1)$$ But we have $$N \prod_{i=1}^{n}\left(1 - \frac{|A_i|}{m_i}\right)$$ $$> N \prod_{i=1}^{n}\left(1 - \frac{|A_i|}{2|A_i|+1}\right)$$ $$= \prod_{i=1}^{n}(|A_i|+1)$$ so the number of such terms is positive, and we are done. Remark: This solution is motivated by first attempting the bounds in case 2 and noting that they solve the problem if $m_i > 2|A_i|+1$ for all $i$. Then if $2|A_i|+1 \ge m_i$ for some $i$, noting the occurence of $2|A_i|+1$ in the upper bound of $N$ in the problem statement, one might hope that somehow we can induct downward on $n$. This gives rise to the generalization.

Inspired by that China TST problem, we want a way to create differences in $Z_{m_i}\backslash A_i$ that have enough elements. Claim: For each $i$, there exist a set with at least $\frac{m_i}{2|A_i|+1}$ elements such that no difference between two elements of this set is in $A_i$. Proof. Consider a graph of the residues modulo $m_i$. Link an edge between $x, x+t$ for all $t\in A_i$. Then note $\deg(v_i)\le 2|A_i|$. By Erdos', there exists an independent set of size at least $\sum\limits_{i=1}^{m_i} \frac{1}{2|A_i|+1}$, so done. Now, let $x_i$ be the solution to $x_i\equiv 1(\bmod\; m_i), x_i\equiv 0(\bmod\; m_j) \forall j\ne i$. We consider $B: \{ \sum b_ix_i : b_i\in B_i\}$. Then $|B|\ge \prod_{i=1}^n \frac{m_i}{2|A_i|+1}$. We can sort the elements of $B=b_1<b_2<\cdots<b_k$, and one of $\prod m_i + b_1 - b_k, b_i-b_{i-1}$ would work by pigeonhole.

Let $n=2013$ be odd. Call a number $k$ as $i$-bad if $k$ is congruent to some value in $A_i$ under $\mod m_i$. Call $N+1$ the minimum number that is neither 1-bad, nor 2-bad, ..., nor $n$-bad. That means each of $1,2,\ldots,N$ are at least one of 1-bad, or 2-bad, ... or $n$-bad. Let $S_i$ be the set of numbers in $1,\ldots,N$ that are $i$-bad. So we know $$\begin{align*} N &= |S_1 \cup \cdots \cup S_n| \\ &= \sum |S_i| - \sum |S_i\cap S_j| + \sum |S_i\cap S_j\cap S_k| - \cdots \end{align*}$$ by PIE. We want to upper bound the above. We'll lower bound and upper bound each term: Claim: For any indices $i_1,\ldots,i_c$, we have $$|S_{i_1}\cap \cdots \cap S_{i_c}| \in |A_{i_1}|\cdot \ldots \cdot |A_{i_c}|\cdot \left[ \frac{N}{m_{i_1}\cdots m_{i_c}}-1, \quad \frac{N}{m_{i_1}\cdots m_{i_c}} + 1 \right].$$ (We abuse interval notation above: $c\cdot [x,y]$ means the interval $[cx,cy]$.) Proof: We will show the stronger fact that $$|S_{i_1}\cap \cdots \cap S_{i_c}| \in |A_{i_1}|\cdot \ldots \cdot |A_{i_c}|\cdot \left[ \left \lfloor \frac{N}{m_{i_1}\cdots m_{i_c}}\right \rfloor, \quad \left \lfloor \frac{N}{m_{i_1}\cdots m_{i_c}}\right \rfloor + 1 \right]$$ which implies the Claim. This is basically just CRT. Examples: Consider just $|S_i|$. Every $m_i$ numbers, there will be exactly $|A_i|$ bad numbers. The set $1,\ldots,N$ splits into $\lfloor N/m_i\rfloor$ blocks of $m_i$, and then a leftover block. So the number of $i$-bad numbers in $1,\ldots,N$ is at least $\lfloor N/m_i \rfloor \cdot |A_i|$ (equality when the leftover block is all good), and at most $(\lfloor N/m_i \rfloor+1) \cdot |A_i|$ (equality when the leftover block is all bad). Consider now $|S_i\cap S_j|$. We want to find the number of values in $1,\ldots,N$ that are $i$-bad and $j$-bad. A number $k$ is $i$-bad means it is congruent to some unique value in $A_i$ under $\mod m_i$, and $j$-bad means its congruent to some unique value in $A_j$ under $\mod m_j$. By CRT, there are hence $|A_i|\cdot |A_j|$ values in $\mod m_i m_j$ that are $i$-bad and $j$-bad. Now similar to the first bullet, we get the claimed bound. Continuing in this logic gives the upper and lower bounds generally. $\blacksquare$ We will alternate using the upper and lower bounds in the Claim now to upper bound $N$: $$\begin{align*} N &= \sum |S_i| - \sum |S_i\cap S_j| + \sum |S_i\cap S_j \cap S_k| - \cdots \\ &\le \sum \left(\frac{N}{m_i}+1\right) |A_i| - \sum \left(\frac{N}{m_i m_j}-1\right)|A_i|\cdot |A_j| + \cdots \\ &= \left[ \sum \left( \frac{N}{m_i} \right)|A_i| - \sum \left(\frac{N}{m_i m_j}\right) |A_i|\cdot |A_j| + \cdots \right] \\ &\qquad + \left[ \sum |A_i| + \sum |A_i|\cdot |A_j| + \sum |A_i|\cdot |A_j| \cdot |A_k| + \cdots \right] \\ &= N\left[1+\left(\frac{|A_1|}{m_1}-1\right)\cdots \left(\frac{|A_n|}{m_n}-1\right)\right] + (|A_1|+1)\cdots (|A_n|+1)-1. \end{align*}$$ Note that the second big sum has all +'s since the alternating +/- from PIE cancels with the alternating +/- from the lower/upper bounds of the Claim. Now subtracting $N$ from both sides and using the fact that $n$ is odd, we rearrange the above to: $$N\le \frac{(|A_1|+1)\cdots (|A_n|+1)-1}{\left(1-\frac{|A_1|}{m_1}\right)\cdots \left(1-\frac{|A_n|}{m_n}\right)}. \qquad (\clubsuit)$$ Note that each term of the denominator is positive since $|A_i|<m_i$ for all $i$. Case 1: $2|A_i| +1 \le m_i$ for all $i$. Then $$\frac{|A_i|+1}{1-\frac{|A_i|}{m_i}} \le \frac{|A_i|+1}{1-\frac{|A_i|}{2|A_i|+1}} = 2|A_i|+1,$$ so from $(\clubsuit)$, $$\begin{align*} N &\le (2|A_1|+1)\cdots (2|A_n|+1) - \frac{1}{\left(1-\frac{|A_1|}{m_1}\right)\cdots \left(1-\frac{|A_n|}{m_n}\right)} \\ &\le (2|A_1|+1)\cdots (2|A_n|+1) - 1, \end{align*}$$ so $N+1 \le \prod (2|A_i|+1)$, done! Case 2: $2|A_i| +1 > m_i$ for some $i$. Simply remove this $i$ and induct down! (This argument is independent of all the solution above.) Indeed, we can basically pretend that the $\mod m_i$ didn't even exist ever, and just take the $N'$ case which has all the indices but $i$ and then use CRT to just add the restriction that they are all some non-$i$-bad value $\mod m_i$. Then we will get that $N \le N'm_i < N(2|A_i|+1)$, as needed.

Solved with a few hints. The induction solution is more motivated than this one. We first prove the following independent lemma. Lemma: Let $m$ be a positive integer and $A \subseteq \{1,\ldots,m-1\}$. Then there exists some $B \subseteq \{0,\ldots,m-1\}$ such that $|B| \geq \frac{m}{2|A|+1}$ and $B-B \cap A = \emptyset$ in $\mathbb{Z}/m\mathbb{Z}$. Proof: Start with $B$ empty and throw in elements arbitrarily as long as they don't cause things to break. Each new element $k$ invalidates $2|A|+1$ others (possibly already invalidated), namely $k$, $k-a$, and $k+a$, where $a \in A$ is some element. $\blacksquare$ By our lemma, create sets $B_1,\ldots,B_{2013}$ such that $B_i-B_i \cap A_i=\emptyset$ in $\mathbb{Z}/m_i\mathbb{Z}$ with $|B_i| \geq \frac{m}{2|A_i|+1}$. Also let $P_i$ be an integer such that $P_i \equiv 1 \pmod{m_i}$ and $P_i \equiv 0 \pmod{m_j}$ for all $j \neq i$. Now the linear combination $$\sum_{i=1}^{2013} b_iP_i \pmod{m_1\ldots m_{2013}},$$ where $b_i \in B_i$ for all $i$. Since there are $\prod_{i=1}^{2013} |B_i|$ such combinations, counting multiplicity, there must be some pair of residues $r_1$ and $r_2$ such that the the mod-$m_1\ldots m_{2013}$ residue of $r_1-r_2$ is at most $$\frac{\prod_{i=1}^{2013} m_i}{\prod_{i=1}^{2013} |B_i|}\leq \prod_{i=1}^{2013} (2|A_i|+1).$$ Pick $N$ equal to $r_1-r_2$, so $N \leq \prod_{i=1}^{2013} (2|A_i|+1)$. We can check that, modulo $m_i$, $N$ is in $B_i-B_i$, which is not in $A_i$, hence $m_i \nmid N-a$ for any $a \in A_i$, so we are done. $\blacksquare$

I wouldn't consider the CRT solution completely unmotivated, but it's quite tricky to get. Let $M = m_1m_2 \cdots m_{2013}$. Per the algorithm associated with CRT, let $\varepsilon_i \equiv 1 \pmod m_i$ and $\varepsilon_i \equiv 0 \pmod m_j$ for $j \neq i$. We will construct sets $B_i$ with $|B_i| \geq \frac{m_i}{2|A_i| + 1}$ for each $i$ such that for any $x, y \in B_i$, $x-y \not \in A_i$. To do this, just use a greedy algorithm: upon adding some element $k$ to $B_i$, every element $k \pm a$ with $a \in A_i$ is eliminated from consideration; this eliminates at most $2|A_i| + 1$ elements at each step, hence the result. To finish, consider all such sums $\sum_{i=1}^{2013} \varepsilon_i b_i$ where $b_i \in B_i$. There are $\frac{M}{\prod_{i=1}^{2013} (2|A_i|+1)}$ such sums, which each correspond to residues modulo $M$ by nature of the $\varepsilon_i$. Thus follows there exist two such sums $S_1$ and $S_2$ that differ by at most $\prod_{i=1}^{2013} (2|A_i|+1)$. Taking $N = |S_1-S_2|$ works.