I have $20$ cards, each labelled $1$ to $20$, and I would like to find the minimum number of cards I have to select such that there will always be $2$ cards in the subset of cards selected, that add up to $21$.
The method I used to solve this question (which I am not sure of) is as follows:
First I list down the possible unique pairs of cards that add up to $21$, which are
$\{1, 20\}, \{2, 19\}, \{3, 18\}, \{4, 17\}, \{5, 16\}, \{6, 15\}, \{7, 14\}, \{8, 13\}, \{9, 12\} ,\{10, 11\}$
and there are $10$ unique pairs.
Then I applied the pigeonhole principle which states that for $kn+1$ pigeons, to be distributed into $n$ holes, there must be at least $k+1$ pigeons in each hole. In this case, I let the pairs be the "holes" and the cards be the "pigeons", and solved for $k$ to get $k=$${19}\over{10}$, and therefore, at least $3$ cards must be selected for there to always have $2$ cards that have a sum of $21$.
I am not sure if my solution is correct, and if I am using the pigeon hole principle correctly, and I think the selection of what to use for the "holes" is wrong. Can someone explain what is the right way to go about selecting the "holes" for this problem?
If I am correct, I am not sure why I am correct and why the selection of the "holes" as the pairs is correct. Can someone explain to me?
Best Answer
The pigeonhole principle is that if $kn+1$ (or more) "pigeons" are divided amongst $n$ "holes" then at least one of the holes contains at least $k+1$ pigeons.
Here, the holes are the pairs (so $n=10$), and you want to conclude that at least one pair contains at least $2$ pigeons, so $k+1=2$.
The answer is the number of cards selected, which corresponds to the number of pigeons. So this is $nk+1=11$.
An example which shows this is best possible is that if you only selected $10$ numbers, they could be the smallest $10$, in which case the maximum sum of any pair would be $19$.