Proof verification - Pigeonhole principle.

Question

The question goes like this:

There are $16$ different integers $a_1...a_{16}\;$ such that foreach $i\; , $ $1\leq i \leq 16\;$ :$1\leq a_i \leq 30\;$.

Prove that there is a pair $a_i,a_j$ such that $a_i + a_j = 31$.

My proof:

There are $\binom{16}{2} = 120$ options to chose a pair, and only $(30+29)-(1+2) = 56$ possible sums.

$\left \lfloor \frac{120}{56} \right \rfloor = 2$

Due to the pigeonhole principle, we must have a pair $a_i,a_j$ such that $a_i + a_j = 31$ because each possible sum must contain a pair.

Is this a legit proof (logically speaking)?

Answer 1

You tagged it as pigeonhole principle, so making concrete pigeonholes might be a good idea. You are looking for pairs that sum to $31$, so those stand out as a natural choice. We then get the pigeonholes $$ \{1,30\}, \{2,29\}, \ldots, \{15,16\} $$ Now apply the principle, and you're done.

Answer 2

To see if it makes sense logically, first ask yourself these questions:

• What is the significance of the number $\left \lfloor \frac{120}{56} \right \rfloor$?
• What does it mean for a sum to "contain a pair"?

If you are struggling with the questions, then perhaps your proof is not complete. Or you might need to find another way to solve it. (Hint: find the smallest pair of numbers that sum to 31, is there any pair $(a_i,a_j)$ that could equal these numbers?)

Answer 3

Your solution does not work. At most it shows that for possible sums the average number of pairs that sum up to that sum exceeds $2$. That does not prove that this is especially the case for sum $31$.

---

Assume that there is no such pair.

Then for each of the following $15$ pairs at least one of the members is not in the set $\{a_i\mid i\in\{1,\dots,16\}\}$:

$$\{1,30\},\{2,29\},\dots,\{15,16\}$$

But if $15$ numbers of $\{1,\dots,30\}$ are deleted then only $15$ will remain.

One too short to fill up the set $\{a_i\mid i\in\{1,\dots,16\}\}$ which has $16$ elements.

Proved is now that the assumption is false.