# Puzzle involving selecting gloves

There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown, 2 pairs of grey. You select the gloves in the dark and check them only after you have made the selection. What is the smallest number of gloves you need to select to guarantee getting the following?

a) at least one matching pair

b) at least one matching pair of each color

-
For b), $19$ is enough, anything less and we may be in trouble. –  André Nicolas Dec 23 '12 at 19:08

HINTS:

(a) If you select $10$ gloves, you might get every left glove in the drawer; what if you select more than $10$?

(b) You could select $16$ gloves and still have only two colors; how? How many more than that are needed to be sure that you actually have a pair of each color?

-
Hi @brian for part a) I was thinking that I would select all of the gloves for the wrong hand. So 5 black gloves, 2 grey gloves, and 3 brown gloves. A total of 10 gloves. And then the next glove I pick would need to be a matching pair? –  МикроПингвин Dec 23 '12 at 19:03
@Justin: You’re right: I was thinking of something without handedness, like socks, rather than gloves. I’ll change the answer. For (b) just use the same kind of thinking. –  Brian M. Scott Dec 23 '12 at 19:07

After deliberation on the responses given for part (a) of this question, I respectfully disagree with the previous answers because they take a naive approach. If you are in the dark, you cannot tell the color of the glove, but you can tell whether the glove is left or right. The above answers did not take that second caveat into consideration. Your algorithm for glove selection was ignorant of handedness, but a human can determine handedness in the dark. Does it matter? Yes!

Let's assume that you start by selecting a left handed glove. You check its color, finding out that it is black. You repeat the process four more times, each time also finding a black left-handed glove. Then you select one more glove, which unluckily happens to be gray. At this point, stop choosing left-handed gloves. Draw a right-handed glove. In the worst case, you will draw three brown right-handed gloves without drawing either a black or grey right handed glove. Finally, you draw one more right-handed glove and it is either black or grey, fulfilling the criteria. This is a total of 10 selections.

Therefore, the smallest number of gloves to draw for part (a) of this question is 10, not 11 as stated by others.

Many other versions of this question use the phrase "worst case". I believe that "worst case" generally assumes that you are using an efficient algorithm. If worst case means the worst algorithm then you draw all the left-handed gloves first and then draw one more right-handed glove. Thus the worst case answer is 11.

-
"In the dark" is generally word-problem-speak for "randomly". –  Joe Z. Aug 28 '13 at 22:31