2
$\begingroup$

$n$ is also given to be an even number.

So I want to prove this by using the pigeon-hole principle.

I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as follows : $$\{1,2\}, \{3,4\},......,\{2n-1,2n \}$$

if $n+1$ numbers are to be chosen from these $n$ boxes, How to show that there will be remaining numbers that differ by 2 ?

Let's say we have $n=4$ then we would have $$\{1,2\} ,\{3,4\}, \{5,6\}, \{7,8 \}$$

Now if we $5$ numbers are chosen from the above, then we want to show that there are two of the three numbers remaining that differ by $2$

Here I have $4$ holes and $5$ pigeons, so one of these pairs must be chosen when choosing the $5$ numbers , But still I can't argue that we will be left with 2 numbers that differ by 2.

ANy suggestions ?

$\endgroup$
  • 1
    $\begingroup$ Note that $n$ being even is crucial. (For example, if $n=3$, then $\{1,2,5,6\}$ is a set of $n+1$ integers which doesn't have this property...) $\endgroup$ – Micah Oct 3 '15 at 20:29
  • $\begingroup$ so How can I use the fact that $n$ is even here ! @Micah $\endgroup$ – alkabary Oct 3 '15 at 20:38
3
$\begingroup$

Why not instead consider: $$\{1,3\},\{2,4\},\{5,7\},\{6,8\},\ldots$$

Alternately:

Pick an element from the set. Now there is at least one element that is ineligible to be picked next, as it is 2 away from the first element. Proceed by induction.

$\endgroup$
  • $\begingroup$ Can we generalise this pattern to $n$ where $n$ is even ? $\endgroup$ – alkabary Oct 3 '15 at 20:46
  • $\begingroup$ @alkabary probably, you asked for a hint, not the full solution. $\endgroup$ – djechlin Oct 3 '15 at 20:49

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.