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(3): huh? by Brian Smith)

"Assume the distribution of gloves was 10 red, 10 green, 10,000 blue. You would need to draw only 21 rights and 21 lefts to guarantee a blue match."

I'll admit that I didn't think of doing it that way. I only thought of picking the same handed glove until I was sure I had all the colors, then picking an opposite hand glove to make a match.

But, after thinking about it more, I still think I'm right. Let me put it like this. The fact that the number of the glove that told you for certain you had a match was 21, tells me that it was done my way. Because done your way it would always be on an even numbered pick, no matter what combination of numbers we use.

Done your way, you would pick one more (of one hand) than the sum of all the colors minus the most common one. Then the same number of the other hand. Given the numbers 15 25 35 1000000, you would be certain of a match with 152 gloves (half left & half right). Picking 75 lefts can give you 75 of the most common color or all of the 3 least common colors (or some other combination of 3 colors or only 2 colors). If you picked all of the least common colors of one hand then start looking for the opposite hand you would need to pick a million and one to be sure you picked another of the least common colors. But if you picked 76 of one hand you can be sure that you have at least one of the most common color so you would need to pick another 76 to be sure you have a match with it

My point is, that doing it that way, you will always find out that you have a match on an even pick. In that case there is no limit to how many gloves there could be. But if you find out on an odd pick then there HAS to be a maximum number of gloves, and that number would be have to be 28 pairs if you find out only after picking 21 gloves that you have a match for the reasons I said before.

Edited on June 4, 2004, 8:09 am

Posted by Danny on 2004-06-04 00:10:11