6 random integers from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, at least one pair will have an odd sum.

Question

I would first like to say that I completely understand why and how this works. In the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, there are 5 even numbers, and 5 odd numbers. Assuming we choose our first 5 numbers with the same parity, all of their sums are even. This is because $even + even = even$ and $odd + odd = even$

However, when we pick our sixth and last number, this number will have the opposite parity, meaning we have at least one odd sum, since $even + odd = odd$.

However, I am having trouble clearly defining what the pigeons and pigeonholes are. At first, I thought it was

Pigeons: 6 integers, at least one will be opposite parity

Pigeonholes: 5 ???s

But after some thought, I think it is

Pigeons: 1 remaining opposite-parity integer

Pigeonholes: 0 acceptable spots for an opposite parity integer in order to maintain even sums

However, this just seems wrong and kind of unintuitive. I would appreciate any help in explicitly defining the pigeons and pigeonholes.

Answer 1

Welcome to MSE!

You have the exact right idea!

Why not let your holes be $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, $\{7,8\}$, and $\{9,10\}$?

Then you're guaranteed $2$ pigeons in the same hole, but the sum of two consecutive numbers is odd.

---

I hope this helps ^_^

Answer 2

Let $n$ be even. Notice that there are $n/2$ even and odd numbers. (The problem is equivalent to choosing $n/2$+$1$ integers from [$n$]). So partition [$n$] into two sets, one containing all of the $n/2$ even numbers, and the other $n/2$ odd numbers. By the pigeonhole principle, there are two integers with opposite parity. Their sum is an odd number.

This problem is the special case when $n$=$10$.