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:
- Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates.
- Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one
- Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d
- Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.
- A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.