Sharon has a number of pairs of gloves of identical design, but of several (at least three) different colors. She has at least three pairs of each color. In the dark she can distinguish the handedness of a glove, but not its color. Unfortunately, she keeps the gloves jumbled up in a drawer in an unlit cellar.

Sharon knows that if she takes out 21 gloves, in the dark, she can be sure of getting at least one pair.

What is the maximum number of pairs of gloves that she could have?

(In reply to re: Solution? by Charlie)

If she knows that it would take at least 21 gloves to make a match, we have to assume that she must know exactly how many gloves she has. IOW, there has to be a maximum. First, she would pick any glove. She would be able to tell if it's left or right-handed. Then she would have to find 19 more gloves of the same hand. At that point she knows that if she picks one more glove of the opposite hand, then she has a match. That means that the minimum number of pairs of gloves that she can have is 22, with 3 pairs of the least common color. She could, however, have 9 pairs of one color (red, for ex.) and 10 pairs of blue and 9 pairs of yellow. That way if she picks 20 gloves of one hand then she can be sure she has all 3 colors (because sum of any 2 colors is 19 or less) That would mean 28 pairs is the max, if she has only 3 colors. If she has more colors, then all her gloves, minus the least common color would have to equal 19 pairs - same as with 3 pairs. 25 would be the max for 4 colors because 6, 6, 6 and 7 would be the set of numbers where any 3 of them equal 19 or less and the lowest number is the highest possible. IOW, any 3 numbers from 5, 6, 6 and 7 also equal 19 or less but then, that's only 24 pairs. With more colors the maximum number of pairs of gloves that she can have will be less. So, the maximum number of pairs she can have is 28, with only 3 colors.

Posted by Danny on 2004-06-03 15:29:56