5

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.

Andrés E. Caicedo
  • 79,201
MasterMorine
  • 53

2 Answers2

2

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$.

Milo Brandt
  • 60,888
1

You've got $n$ pigeonholes, each one with two numbers in it (which add to $2n+1$). Now try to take $n+1$ numbers without emptying one of the pigeonholes...

... and of course you can't - two of our choices must come from the same pigeonhole (even if we don't know which one).

The basic idea of the pigeonhole principle is that if you have more items than categories, some categories must have more than one item. Here the categories are the pairs of numbers that add to $(2n+1)$ - there are $n$ of those pairs, and every number in range is uniquely in one of those categories - and you want to select more than $n$ items from those categories.

Joffan
  • 39,627