How many numbers must be selected from the set {1,3,5,7,9,11,13,15,17} to guaran
ID: 2965309 • Letter: H
Question
How many numbers must be selected from the set {1,3,5,7,9,11,13,15,17} to guarantee that at least one pair of these numbers have an average of 9?
I used Pigeonhole principle: Ceiling function(N/k). Atleast one box contains at least (N/k) objects. Four pairs have an average of 9. I end up with 5 numbers must be selected, however 9 is in the set and does not pair with any number (unless it is with itself) to an average of 9. This is my doubt, do I just add one extra number must be selected? If so, what is the proof that you must add this extra number.
Explanation / Answer
Yes, you just add 1. We may partition the 9 numbers into 5 subsets
(1, 17); (3, 15); (5, 13); (7, 11) (9)
We may select one number from each of the 5 subsets and we will have no numbers that pair. However, if we select a 6th number from 5 sets, by the pigeonhole principle, we will have to have 2 numbers from at least one of these sets, which means that we will have at least one pair. Thus, 6 numbers are required to guarantee a pair.