Fdtxjr

When $n$ is an integer such that $n>1$, $S$ is an arbitrary subset of $1,2,3,...,3n$ and the number of elements of $S$ is $n+2$, prove that there exist integers $x, y$ in $S$ such that $n<y-x<2n$.

more information)

with out loss of generality, there exists $3n$ in $S$ (I don't know the reason..)

when the intersection of $[n+1,2n-1] $ and $S$ is not empty,
there exist integers $x, y$ in $S$ such that $n<y-x<2n$.

then, what about the intersection of $[n+1,2n-1] $ and $S$ is empty..?

$newcommandset[1]left#1right$ EDIT: To help make the argument clearer, here is a description of the argument. The claim is that for any subset $S$ of the $3n$ consecutive integers $1,ldots, 3n$ which contains $n+2$ elements, there is a pair of elements in the subset whose difference lies between $n$ and $2n$. For example, if $n=2$ and the set is $set1,2,3,4,5,6$, we want to show any set of $4$ elements has a pair whose difference is $3$. This is easy to see by checking all possibilities in this instance, but that is impractical for larger $n$, much less to prove the statement in general.

Instead, we will use a divide and conquer approach. The first part of the argument will reduce the problem significantly, without loss of generality, by showing that the set $S$ can always be assumed to contain the largest element, and thus it suffices to prove the statement in the case that $S$ contains $3n$ and none of the elements in the middle third $n+1,ldots, 2n-1$. This allows us to apply the pidgeonhole principle by splitting the remaining possible elements of $S$ into pairs whose difference lies in the desired range, and showing that $S$ must contain one of those pairs.

The Strategy

First, note that this is really a question about the set of differences $delta S$ generated by the subset $S$. For example, when $n=2$ and $S=set1,2,4,6$, we have $2-1=1$, $4-2=6-4=2$, $4-1=3$ $6-2=4$, and $6-1=5$, hence the set of differences is $delta S=set1,2,3,4,5$. (Here, we exclude the negative differences as we will always have $x-y$ or $y-x$ in $delta S$ as defined.) The claim then is that one of these differences lies between $n$ and $2n$.

To prove the claim, first we simplify by noting we can always assume $3nin S$. This is because the differences don't change if we shift every element of $S$ by the same amount; for example, if $S=set1,2,3,4$, and $S+2=set3,4,5,6$, the differences $delta S=set1,2,3=delta(S+2)$ are the same. In particular, if there were some $S$ such that the claim were false, there would be an $S$ containing $3n$ also proving the claim to be false.

If $S$ contains $3n$ and any of the elements between $n$ and $2n$ steps away (namely, $n+1, n+2,ldots, 2n-1$), then we would be done. For instance, if $n=2$ and $3in S$, then $3=6-3in S$ proving the claim. So there is only more to argue if we assume those elements are not in $S$.

In that case, we have that $S$ contains $3n$ and some other elements $S'$ which live in $1,2,ldots, n$ or $2n,2n+1,ldots, 3n-1$. (E.g. in the $n=2$ example,
if $6in S$ and $3notin S$, then the remaining 3 elements of $S$ must be elements of $set1,2,4,5$.) We can pair these elements together as $set1,2n$, $set2,2n+1,ldots, setn,3n-1$ where the pairs are of the form $setk,2n-1+k$. (So in the $n=2$ case, the pairs are $set1,4$ and $set2,5$.)

Now to prove the claim in this case, we use the pidgeonhole principle. To do so, we need our pidgeons and our holes. The pidgeons in this case are the elements of $S'$ (i.e. the elements of $S$ other than $3n$) and the holes are our pairs $setk,2n-1+k$. Each pidgeon lives in one of the holes, but there are $n+1$ pidgeons and $n$ holes, so two pidgeons must share a hole. (The formal way of putting this is defining a function and concluding its not one-to-one.)

But if two distinct elements of $S$ belong to the same pair, their difference is $2n-1$ by construction, hence the claim follows. (Indeed, in our example, our subset $S$ must contain all but one of $1,2,4,5$, but if it contains both 1 and 4, or both 2 and 5, those elements have a difference in the required range.

The proof:

Suppose $S$ is a subset of $[1,3n]_mathbb Z=set1,ldots, 3n$ with $|S|=n+2$.
Let $delta S=setx-y$. The claim can be formulated as $[n+1,2n-1]_mathbb Zcap delta Sneq emptyset$; if there is some $x,yin S$ such that $n<y-x<2n$, then $y-xin setn+1,n+2,ldots, 2n-1=[n+1,2n-1]_mathbb Z$, but also $y-xin delta S$ by definition, hence is an element of the intersection.

Note that for any $ainmathbb Z$, if $S+a=sets+amid sin Ssubset [1,3n]_mathbb Z$, then $delta(S+a)=delta S$ (since for any $x,yin S$, $x+a,y+ain S+a$ and $|x-y|=|(x+a)-(y+a)|$, so we can freely translate $S$ without effecting the claim. In particular, we can assume $3nin S$; otherwise, there is some maximal $min S$, and we can consider the set $S+(3n-m)$.

If $3nin S$, then the claim follows if $[n+1,2n-1]_mathbb Zcap Sneq emptyset$, as any $n+1leq xleq 2n-1$ satisfies $n+1leq 3n-xleq 2n-1$. Then we are reduced to considering the case that $[n+1,2n-1]_mathbb Zcap S= emptyset$. Let $S'=Ssetminus set3n$ and note that $S'subseteq set1,ldots, n, 2n,ldots, 3n-1$. Define a new set of sets $$mathcal P=setsetk,2n-1+kmid 1leq kleq n=setset1,2n,set2,2n+1,ldots,setn,3n-1.$$
(In other words, we pair up the elements of $set1,ldots, n, 2n,ldots, 3n-1$ into subsets $setx,y$ so that $|x-y|=2n-1$.)
Since any element $sin S'$ belongs to exactly one $Pinmathcal P$, we have a function $p:S'rightarrow mathcal P$ defined by $p(s)= P$ where $sin P$. Since $|S'|=|S|-1=n+1$ and $|mathcal P|=n$, the Pidgeonhole Principle implies $p$ is not one-to-one, hence there is some $xneq yin S'subset S$ such that $setx,yin mathcal P$, which implies $|x-y|=2n-1$.

The proof does not explicitly require the pigeon hole principle.

1) For the inequality $n<y-x$, one should choose as many elements of $S$ as possible which are at close proximity; this will keep $y-x$ small.

More concretely, I choose $n$ consecutive elements in $S$, $$a<a+1<ldots<a+(n-1).$$
For those elements, the difference is at most $n-1$. But you have to choose two additional elements $b,c$ with say $b<c$ outside the above chain. There are two cases: (1) If $b<c<a$, then $a+(n-1) - b > n$. (2) If $b<a$ and $a+(n-1)<c$, then $c-b>n$. Done.

2) For the inequalty $y-x<2n$, one should choose as many elements of $S$ as possible which are very far apart; this will make $y-x$ large.

More concretely, I choose $n$ elements in $S$ which can be divided into two groups and have a large gap in between:
$$1<2<ldots<n-a ;mboxand; 3n-a+1<3n-a+2<ldots<3n.$$
The size of the gap is $(3n-a+1)-(n-a) =2n+1$. Now you have to add two elements $b,c$ with say $b<c$. Since $b,c$ are inserted into the gap, $c-b<2n$. Done.