# The drawer has M different colored socks. What is the least amount of socks I that I need to draw to guarntee N pairs

So in my discrete math class, we all know that if the drawer has 2 different colored socks, you need to pull out 3 socks to ensure a pair.

However, I am puzzled after there are more different colored socks and more pairs of socks.

For example, if there are 3 different colored socks in the drawer and I need to draw out 50 pairs, at least how many socks do I need to draw out to ensure that I have 50 pairs of sock?

How about if there are M different colored socks in the drawer and I need to draw out N pairs, at least how many socks do I need to draw out to ensure that I have N pairs of sock?

Are there any general formulas for these types of problem? Or are there any rules for this type of question?

#### Solutions Collecting From Web of "The drawer has M different colored socks. What is the least amount of socks I that I need to draw to guarntee N pairs"

The maximum is clearly achieved when there is an odd quantity of socks of each color(A proof by contradiction is immediate). If you have $2c_1+1,2c_2+1,\dots ,2c_M+1$ socks of each of the $M$ colors then you have $c_1+c_2\dots +c_m$ pairs and $2(c_1+c_2+\dots c_M)+m$ socks. Then the maximum socks you can have without $N$ pairs is $2(N-1)+m$