$6967$ notes labelled $1,2,3,4,...,6967$,choose $K$ notes at random,the smallest number $K$ to ensure that two notes labelled by consecutive numbers?

Question

There are $6967$ notes labelled $1,2,3,4,...,6967$. If you choose $K$ notes at random, what is the smallest number $K$ that would guarantee that you pick two notes labelled by consecutive numbers? Use the pigeonhole principle to explain

I'm not quite sure in this question what the pigeons and pigeonholes are. If someone could explain that would be great

Answer 1

Picking all the odd numbers gives a maximal set without neighbours and $3484$ elements. Divide the set in $\{1,2\}$, $\{3,4\}$, ..., $\{6965,6966\}$, and $\{6967\}$; that's $3484$ pigeon holes, so if you pick $3485$ numbers at least one pigeon hole gets picked from twice.

Answer 2

The pigeonhole principle is summarized as the following

If $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item.

It's quite a simple concept, but a powerful one. Let's think about how to apply it in your problem.

We realize immediately that there are two "pigeonholes" for us to consider in this problem: even and odd integers. It's obvious that no even numbers can be consecutive, and neither can any odds. So, we try to fill in as many numbers from one "pigeonhole" as we can (in this case, we can fill in the $3484$ odd integers) and then add one more to force there to be two consecutive integers (since the last number must be even.) Hence, the answer is $\color{red}{3485}$.