How many numbers must be selected from the set {1,3,5,7,9,11,13,15,17} to guaran

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.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.