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?
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$