Can anyone point me in the right direction for this homework question? I know what the pigeonhole principle is but don't see how it helps 🙁
Let $n\geqslant 1$ be an integer and consider the set S = {1,2,…..,2n}. Let T be an arbitrary subset of S having size n + 1. Prove that this subset T contains two elements whose sum is equal to 2n + 1.
The hint we were given is "Consider the pairs (1,2n), (2, 2n-1), (3, 2n-2),….,(n, n+1) and use the pigeonhole principle"
Any help would be great 🙂
I haven't tried anything because I have no idea where to start.
Best Answer
Imagine the following array: $$\begin{array}[cccccccccc] .1 && 2 && 3 && 4 && \ldots && n-2 && n-1 && n \\ 2n && 2n-1 && 2n-2 && 2n-3 && \ldots && n+3 && n+2 && n+1\end{array}$$
Notice that each column sums to $2n+1$ and all of the numbers from $1$ to $2n$ are used in the array. There are $n$ columns. What you want to prove is that if you were to highlight $n+1$ numbers in this array (i.e. the elements of $T$), there would be a whole column highlighted, and that pair would sum to $2n+1$.
The pidgeonhole principle essentially says that we cannot possibly highlight $n+1$ numbers such that no two lie in the same column, if there are but $n$ columns. If you want to see this, then just take a small array, like for $n=3$: $$\begin{array}.1 && 2 && 3\\6 && 5 && 4\end{array}$$ Now, let's start highlighting some numbers, trying to avoid putting two in a column. Our goal is to highlight $4$ numbers, as that is the size of the set $T$. We could start by putting $1$ in $T$: $$\begin{array}.\color{red}1 && 2 && 3\\6 && 5 && 4\end{array}$$ but now we know we can't put $6$ in $T$ too, because that would sum to $2n+1$. So we might choose $5$ as our next number, forbidding $2$ and we might choose $4$ as the number after that: $$\begin{array}.\color{red}1 && 2 && 3\\6 && \color{red}5 && \color{red}4\end{array}$$
So, now we have a highlighted number in every column- and adding any further number to the set $T$ would create a pair summing to $7$. But this means that we can't have a fourth element in $T$, at least given how we started - and the pidgeonhole principle guarantees that we can never choose a set of size $4$ without putting two elements in one column.
The key point here is that we should imagine that, as we're creating $T$, we're not choosing numbers to put in it, we're choosing which column to take the numbers from. There are $n$ columns, and we need to make $n+1$ choices - thus we will, at some point, choose the same column twice, and in this context, that means we need to have both elements of some column in $T$, and this forms a pair summing to $2n+1$.