A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.

Let’s revisit the two principles that apply to this type of exercise.

“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 socks must he take out to be sure that he has at least two socks of the same color?

In this case, we can apply the pigeonhole principle by thinking about the colors of the boxes mentioned in the principle.

So, by the pigeonhole principle, we need k+1=3 objects (k is the number of boxes, 2 in this case).

He must take out at least 3 socks to be sure that 2 have the same color.

Another way to solve this exercise is by using the generalized pigeonhole principle. In this case, we know that we want one box containing at least 2 objects (this is the only way we will get two socks of the same color) and we have two boxes. It follows that ⌈N/2⌉=2, then N=3.

b) How many socks must he take out to be sure that he has at least two black socks?

In the worst-case scenario, he can take first all the brown socks (12), and the next 2 will be black.

So, he must take out 14 socks for him to be sure that 2 of them are black.

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
• A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them
• Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.