5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You have $n$ pairs, and the set $T$ has $n+1$ members, so two members of $T$ must ... ? $\endgroup$ – Brian M. Scott Jan 27 '15 at 23:56
  • $\begingroup$ ...be in S. I just don't see how it helps i guess $\endgroup$ – MasterMorine Jan 27 '15 at 23:59
  • $\begingroup$ it will be helpful for you to pick a small $n,$ say $3$ write out all the subsets of size $4.$ $\endgroup$ – abel Jan 28 '15 at 0:00
  • 1
    $\begingroup$ All members of $T$ are in $S$ by definition. Think of the members of $T$ as the pigeons, and the pairs as pigeonholes ... $\endgroup$ – Brian M. Scott Jan 28 '15 at 0:00
  • $\begingroup$ Okay, get what I'm to think of them as, but how do I use that? $\endgroup$ – MasterMorine Jan 28 '15 at 0:05
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ...how exactly? Were told what the pigeonhole principle is but not applications of it exactly $\endgroup$ – MasterMorine Jan 28 '15 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.