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.

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

share|improve this question
    
For b), $19$ is enough, anything less and we may be in trouble. –  André Nicolas Dec 23 '12 at 19:08
add comment

3 Answers

up vote 3 down vote accepted

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?

share|improve this answer
    
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
2  
@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
add comment

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.

share|improve this answer
    
"In the dark" is generally word-problem-speak for "randomly". –  Joe Z. Aug 28 '13 at 22:31
add comment

In general, to do this sort of problem, you want to find the "worst-case scenario" – in this case, the greatest number of gloves you can select that don't fit the conditions you've set out. Then, selecting any more will satisfy the conditions.

For example, selecting either white or grey socks out of a drawer, the most you can pull out without having a matching pair is two - one white and one grey. The third one must be either one of the two colours, meaning that there is at least one matching pair.

In this case, the gloves can either be left or right gloves, which puts another condition on the problem.

a) The most gloves you can have without a single matching pair is all the gloves of a single hand. So if you have more than 10 gloves (at least 11), at least one of them will be a matching pair.

b) The most gloves you can have without a matching pair of each colour is all the gloves except the gloves of one hand and one colour (so that you never have a matching pair of that colour). For example, if you have none of the left black gloves, you'll never have a black pair, and you have 15 gloves. However, it's possible to do better than this. Which colour will give you the worst-case scenario?

share|improve this answer
add comment

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.