Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've worked out the answer to this as 13 since it's common sense, but we are supposed to apply the pigeon-hole principle, and I don't see how it is applicable here.

A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them. How many balls must she select to be sure of having at least 3 blue balls?

share|improve this question
    
I agree with you, I don't see the applicability. –  muzzlator Feb 28 '13 at 14:39

1 Answer 1

up vote 1 down vote accepted

One can imagine an embellishment to the general pigeon-hole picture to make the principle apply. Imagine 12 pigeon-holes, and that we are enforcing these rules: you use empty spots first when they are available; you can only put red balls in the first ten slots; you can only put blue balls in the last two slots.

The pigeon-hole principal says that if 13 balls are sorted into these pigeon-holes, that at least one of the slots has two balls in it. If one of the white slots has 2 balls that means, according to our rules, that there are at least 11 white balls (a contradiction to the limited supply of white balls.) Since that cannot happen, there must be a spot with two blue balls. Again according to our rules, that means we filled the two blue slots and then added another blue. So, there must be at least three blue balls.

To show this is minimal, you just point out that selecting 10 whites and 2 blues shows that 12 is not sufficient.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.