I think that some PHP will help here.

This can be solved by double counting.

Any solution $?$

Assume that any $S$, a positive integer $n$ such that there are less than $69$ positive integers $x$ such that $x, x+n \in S$ Let $S_{i}=\{x+i | x \in S \} $ ($i$ is non-negative integer) so for any $i < j$, $|S_i \cap S_j| = |S_0 \cap S_{j-i}| \leq 69$ for positive integer $k$, $X_k=\{(S_i, x) | i=0, 1, 2, . . . , k, x\in S_i\}$ $Y_k=\{(S_i, x), (S_j, x) | x=0, 1, 2, . . . , 2000+k, 0 \leq i < j \leq k, (S_i, x)\in X_k, (S_j, x)\in X_k\}$ $|Y_k| = \sum_{0 \leq i < j \leq k} |S_i \cap S_j| \leq \frac{69(k+1)k}{2}$ . . . . . . $A$ let $p_{k, i}=|\{(S_i, j) | (S_i, j) \in X_k\} |$ $\sum_{j=0}^{2000+k} p_{k, j}= |X_k|=\sum_{i=0}^k |S_i|=401(k+1)$ $|Y_k|=\sum_{j=0}^{2000+k} \dbinom {p_{k, j}}{2}=\frac{1}{2} \left(\sum_{j=0}^{2000+k} p_{k, j}^2-\sum_{j=0}^{2000+k} p_{k, j} \right) \geq \frac{1}{2} \left[\frac{\left(\sum_{j=0}^{2000+k} p_{k, j} \right)^2}{2001+k}-\sum_{j=0}^{2000+k} p_{k, j} \right]$ $=\frac{401^2(k+1)^2}{2(2001+k)}-\frac{401(k+1)}{2}$ . . . . . . . . $B$ from $A, B$, $69k \geq \frac{401^2(k+1)^2}{2001+k}-401$ $\longleftrightarrow 69k^2-22331k+641600 \geq 0$ from this one, it is false. so the problem is true

I solved it hard, but I believe there's more good solution

My idea is same as you, but looks like I found something different to you and can someone check my solution? Let $S=\{x_1,x_2,...,x_{401}\}$ with $x_1<x_2<...<x_{401}$. Now suppose for the contradition. Define $S_i=\{x+i | x\in S\}$ with $i=0,2000$ Then $|S_i\cap S_j|=|S_0\cap S_{|i-j|}$ for $i,j$ distinct, this is, because, if we minus every elements of each set with something, then the common element won't change. Hence $S=\sum_{0\leq i<j\leq 2000} |S_i\cap S_j|\leq 69\binom{2001}{2}$ We count this sum in different way:

$S=\sum_{i=1}^{400} (x_{i+1}-x_i)(\binom{i}{2}+\binom{401-i}{2})+(x_1-x_{401}+2000)(\binom{401}{2})$ $\Leftrightarrow S=\sum_{i=1}^{400}(x_{i+1}-x_i)((\binom{i}{2}+\binom{401-i}{2}-\binom{401}{2})+2000\binom{401}{2}\geq \sum_{i=1}^{400}(\binom{i}{2}+\binom{401-i}{2}-\binom{401}{2})+2000\binom{401}{2}$ A bit caculate, this show us from two ways: $149.653.200\leq 138.069.000$, contradition! Hence, the result follows

Has someone an more beautiful solution?

Vietnamisalwaysinmyheart wrote: My idea is same as you, but looks like I found something different to you and can someone check my solution? Let $S=\{x_1,x_2,...,x_{401}\}$ with $x_1<x_2<...<x_{401}$. Now suppose for the contradition. Define $S_i=\{x+i | x\in S\}$ with $i=0,2000$ Then $|S_i\cap S_j|=|S_0\cap S_{|i-j|}$ for $i,j$ distinct, this is, because, if we minus every elements of each set with something, then the common element won't change. Hence $S=\sum_{0\leq i<j\leq 2000} |S_i\cap S_j|\leq 69\binom{2001}{2}$ We count this sum in different way:

$S=\sum_{i=1}^{400} (x_{i+1}-x_i)(\binom{i}{2}+\binom{401-i}{2})+(x_1-x_{401}+2000)(\binom{401}{2})$ $\Leftrightarrow S=\sum_{i=1}^{400}(x_{i+1}-x_i)((\binom{i}{2}+\binom{401-i}{2}-\binom{401}{2})+2000\binom{401}{2}\geq \sum_{i=1}^{400}(\binom{i}{2}+\binom{401-i}{2}-\binom{401}{2})+2000\binom{401}{2}$ A bit caculate, this show us from two ways: $149.653.200\leq 138.069.000$, contradition! Hence, the result follows wouldn't it be kind of Abel summation?

mamouaz1 wrote: Has someone an more beautiful solution? As a guy above said, this can be proved by double counting. In Hungary (translated), we called this two-rowed pigeonhole principle. I am not a "master" of it, don't quite remember it but I have a book I finished back then which had a part of these problems, might look into it in some days then try to solve this similarly. Try to search problems like this. I knew one with a tennis player/chess master who was training for a competition for like a year so he every day at least once, but trained at max 13 times a week, proove that there were 20 consecutive days that he played exactly $n$ matches (I don't remember n)