Matching Socks and Shoes

1. I have ten black and ten brown socks loose in a drawer. In the dark, what is the least number of socks I must pull out to ensure myself that I have a matching pair?
2. In my closet I have ten different pairs of jogging shoes all lying loose. In the dark, what is the least number of shoes that I must pull out to ensure myself that I have a matching pair?
Source: NCTM Mathematics Teacher

SOLUTION
1. Matching Socks
Let B represent a black sock and b represent a brown sock. Socks are identical so the order of pulling them out is not important and they can go on either the left foot or the right foot. The maximum number of socks I can pull out of the drawer equals 20.
I may be lucky and have a matching pair of socks when I pull out
BB
bb
But, I will certainly have a matching pair when I pull out
bBb
\;bBB
bbb
BBB
The least number of socks I must pull out to ensure myself that I have a matching pair equals 3.

2. Matching Shoes
Let L_1R_1,L_2R_2,L_3R_3,\cdots,L_{10}R_{10} represent the ten different pairs of shoes. Though shoes are different the order of pulling them out is not important and unlike socks left shoes can only go on the left foot and right shoes on the right foot. The maximum number of shoes I can pull out of the drawer equals 20.
I may be lucky and have a matching pair of shoes when I pull out
L_1R_1
L_2R_2
\cdots
L_{10}R_{10}
But, I will certainly have a matching pair when I pull out
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_1
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_2
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_3
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_4
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_5
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_6
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_7
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_8
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_9
L_1L_2L_3L_4L_5L_6L_7L_8L_9L_{10}R_{10}

R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_1
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_2
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_3
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_4
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_5
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_6
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_7
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_8
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_9
R_1R_2R_3R_4R_5R_6R_7R_8R_9R_{10}L_{10}
The least number of shoes I must pull out to ensure myself that I have a matching pair equals 11.

Answer:
1. 3
2. 11

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s