Thread: 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 and consider the function that sends each sock to its color, as shown below in Figure 1.


Figure 1


If , could be a one-to-one correspondence (if the two socks pulled out were of different colors). But if , then the number of elements in the domain of is larger than the number of elements in the co-domain of . Thus, by pigeonhole principle, is not one-to-one: for some . 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?

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 and consider the function that sends each sock to its color, as shown below in Figure 1.


Figure 1


If , could be a one-to-one correspondence (if the two socks pulled out were of different colors). But if , then the number of elements in the domain of is larger than the number of elements in the co-domain of . Thus, by pigeonhole principle, is not one-to-one: for some . 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.

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.