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)?
Best Answer
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.