Results 1 to 3 of 3

Math Help - Pigeonhole principle and minimum numbers of socks matching problem related

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    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.

    Pigeonhole principle and minimum numbers of socks matching problem related-figure1.png
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Pigeonhole principle and minimum numbers of socks matching problem related

    Quote Originally Posted by x3bnm View Post
    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.

    Click image for larger version. 

Name:	Figure1.png 
Views:	13 
Size:	11.2 KB 
ID:	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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Pigeonhole principle and minimum numbers of socks matching problem related

    Quote Originally Posted by Drexel28 View Post
    In your solution there is no need why drawing two MUST give you pair--the fact that it can happen is irrelevant.
    Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. PigeonHole Principle
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 13th 2011, 06:25 AM
  2. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 04:46 PM
  3. Replies: 2
    Last Post: August 28th 2011, 03:19 AM
  4. pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2010, 02:12 PM
  5. Replies: 2
    Last Post: February 16th 2009, 08:30 AM

/mathhelpforum @mathhelpforum