# Pigeonhole principle and minimum numbers of socks matching problem related

• Aug 25th 2011, 04:03 PM
x3bnm
Pigeonhole principle and minimum numbers of socks matching problem related
Suppose a math problem is given:

A drawer contains ten black and ten white socks. You reach in and pull some out without looking at them. What is the least number of socks you must pull out to be sure to get a matched pair? Explain how the answer follows from the pigenhole principle.

Solution in the book:
Let the socks pulled out be denoted $s_1, s_2, s_3, ..., s_n$ and consider the function $C$ that sends each sock to its color, as shown below in Figure 1.

Attachment 22128
Figure 1

If $n = 2$, $C$ could be a one-to-one correspondence (if the two socks pulled out were of different colors). But if $n > 2$, then the number of elements in the domain of $C$ is larger than the number of elements in the co-domain of $C$. Thus, by pigeonhole principle, $C$ is not one-to-one: $C(s_i) = C(s_j)$ for some $s_i \neq s_j$. This means that if at least three socks are pulled out, then at least two of them have the same color.

My solution and question:
But what will happen when i pick black sock first and then I pick black sock again. Shouldn't another solution be that at least two picking of black socks is necessary in order to get a matched pair? Why am i wrong in this matter? Isn't there a chance of picking two of the same colored socks by first two consecutive picking?
• Aug 25th 2011, 08:45 PM
Drexel28
Re: Pigeonhole principle and minimum numbers of socks matching problem related
Quote:

Originally Posted by x3bnm
Suppose a math problem is given:

A drawer contains ten black and ten white socks. You reach in and pull some out without looking at them. What is the least number of socks you must pull out to be sure to get a matched pair? Explain how the answer follows from the pigenhole principle.

Solution in the book:
Let the socks pulled out be denoted $s_1, s_2, s_3, ..., s_n$ and consider the function $C$ that sends each sock to its color, as shown below in Figure 1.

Attachment 22128
Figure 1

If $n = 2$, $C$ could be a one-to-one correspondence (if the two socks pulled out were of different colors). But if $n > 2$, then the number of elements in the domain of $C$ is larger than the number of elements in the co-domain of $C$. Thus, by pigeonhole principle, $C$ is not one-to-one: $C(s_i) = C(s_j)$ for some $s_i \neq s_j$. This means that if at least three socks are pulled out, then at least two of them have the same color.

My solution and question:
But what will happen when i pick black sock first and then I pick black sock again. Shouldn't another solution be that at least two picking of black socks is necessary in order to get a matched pair? Why am i wrong in this matter? Isn't there a chance of picking two of the same colored socks by first two consecutive picking?

In your solution there is no need why drawing two MUST give you pair--the fact that it can happen is irrelevant.
• Aug 27th 2011, 08:26 AM
x3bnm
Re: Pigeonhole principle and minimum numbers of socks matching problem related
Quote:

Originally Posted by Drexel28
In your solution there is no need why drawing two MUST give you pair--the fact that it can happen is irrelevant.

Thanks.