A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them

Let’s start with the following definitions.

THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.”

THE GENERALIZED PIGEONHOLE PRINCIPLE: “If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.”

Source: Discrete Mathematics and its Applications by Rosen.

a) How many balls must she select to be sure of having at least three balls of the same color?

Let’s have two boxes, one for the red balls and the other one for the blue balls.

By the generalized pigeonhole principle, we have that ⌈N/2⌉=3. Notice from the definitions that N is the number of objects we will place in the k boxes. Which in this case is the answer to the exercise.

It follows that N=5.

She must select 5 balls to be sure of having at least three balls of the same color.

b) How many balls must she select to be sure of having at least three blue balls?

In this case, we can look at the worst-case scenario. She selects all reds first, then start with the blue ones.

There are 10 red balls. It follows, that she must select 13 to be sure of having at least three blue balls.

Related exercises: