## 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$.