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?

Since Sharon has at least 3 pair of each color, the maximum number of colors she can have is 7.  With 7 colors and 3 pair in each color, she could be assured to get at least one match by drawing only 20 gloves from the drawer.

If Sharon had 3 pair in each color with 8 colors (24 pair total), it would be possible to draw 21 gloves (all three right handed gloves from 7 different colors) and up to 3 left handed gloves from the 8th color without a match.

Hmmm... ...going back to 3 pair in 7 colors, it would be possible for sharon to draw 18 right handed gloves (all 3 of 6 different colors) and 3 left handed gloves from the 7th color without getting a match, but that wouldn't maximize her probability of finding a matching pair.

We know that with 3 pair in 7 colors Sharon can get a match by drawing 19 right handed gloves ( this assures 1 of each color) and one left handed glove for a total of 20 gloves.  If there are 4 pair of one color, then she will have to draw 20 right handed gloves to assure at least 1 of each color then draw 1 left handed glove for a match.  If two colors have 4 pair, then Sharon would have to draw a total of 22 gloves, so Charlie's earlier proclamation that the maximum number is 22 seems to be correct.

With two colors, you need at least three pair of color 1 leaving 19 pair of color 2 (using 22 as the magic number).  Sharon would have to draw 20 right handed gloves to assure she had at least one of each of the two colors and 1 left handed glove for a total draw of 21!

I say Charlie was right.

Posted by Erik on 2004-06-03 17:26:24