2
$\begingroup$

Now I understand it.

I just learnt this principle. I am doing a problem in which there's a box with many red socks, green socks and blue socks. First question was how many minimum socks should I pick out without looking to be absolutely sure to get a matching pair. This was an intuitive one. However, I am having trouble understanding an extension of this problem: how many socks should I pull out without looking to be absolutely sure that I have a three pairs of a color.

The book said 3 pairs. I presume it is 3 pairs of one color. When I thought about it, I cannot understand why there should be a solution at all. How can I be absolutely certain, when I can pick out a red sock, a red sock, a red sock, infinite number of times. If I dont understand this, then I cannot proceed with learning this principle, as I do not see how it applies or relates.

  • 0
    Presumably, "many" red socks does not mean an infinite number of red socks?2011-05-11
  • 0
    yes I have been thinking about the wrong question. three pairs of one color are desired2011-05-11
  • 1
    By the way, an "infinite version" of the pigeonhole principle can be interpreted in terms of cardinal numbers. See http://en.wikipedia.org/wiki/Pigeonhole_principle#Infinite_sets (for instance) for more details.2011-05-11
  • 0
    @DJC Thanks, but I don't really see any application of that... anywhere. So there can be no injection from the set of natural numbers to the set of reals.. so?2011-05-11
  • 0
    @yayu, does this mean that you no longer take issue with the problem?2011-05-11
  • 0
    @yayu: The "infinite version" of the pigeonhole principle does not apply to your original problem. It was just an FYI...perhaps the comment should have gone under the answer below from Sebastien.2011-05-11
  • 0
    @yayu: I imagine you got $4$ for the first question. The second question cannot be answered, unless you were given some additional information that you have not supplied. The best one can do with no information is to let $m$ be the number of socks (not pairs of socks) of the least popular colour. Then picking all but $m-2$ of the socks will guarantee a matching pair of each colour.2011-05-11
  • 0
    @DJC yes, to verify my understanding. I have to pick out n socks to ensure that I have atleast 6 socks of say red, from the infinite pool. This is a finite problem now, as the "pigeonholes" or colours are finite and $=3$. That means for 6 socks (pigeons) to be in the red-hole, there should be atleast 16 pigeons.. i.e for x holes and n +1 socks, one hole should have nx+1 socks.2011-05-11
  • 0
    @yayu: Three pairs of some colour is straightforward. If you have $15$ pigeons, they might be $5$ to a pigeonhole. But if you have $16$, then at least one pigeonhole has at least $6$ pigeons, so the answer is $16$.2011-05-11
  • 0
    @user6312 colour irrelevant, now that is a third _type_. Could you explain how you got 8 though (still interested)2011-05-11
  • 2
    @yayu: The question keeps changing! To guarantee at least $3$ matching pairs, colour irrelevant, you need $8$ socks. Why? because "worst" cases are $5$-$1$-$1$ and $3$-$3$-$1$, or a permutation thereof. Any additional sock brings you over the top.2011-05-11
  • 0
    @user6312 you deleted and reposted your earlier comment, so now my response appears anachronistic. I have changed this question once, and acknowledged it in 2 comments. I have also used strike instead of delete to make clear what changes Ive made. In my earlier comment I'd asked how you got 8, but in the time being Ive understood it, so +1 to your comment anyway for showing a _third_ modification. PS: _first_ was one with no solution, i.e three pairs of different color Ans:NaN, _2nd_ was my interpretation,i.e 3 pairs of one color, Ans: 16 and _third_ is yours, 3 pairs, color irrelevant, ans: 82011-05-11

2 Answers 2

2

I think the pigeonhole principle applies to sets with a finite number of elements. In which case, you cannot pick up red socks forever. It might last for a time, but you will always end up with one green or blue sock...

  • 0
    you are right. the question I posted is wrong. Three pairs each of one color are desired.2011-05-11
  • 0
    which i was able to solve. But I should have thought this up before doubting myself ;)2011-05-11
4

In the first question, you presumably had an answer of 4, since after 3 socks you either already had a pair or had three odd socks, and so with 4 socks you must have a pair.

In your new version of the second question, you do the same. At some stage the worst case is that you have two pairs of each colour and three odd socks (all the pigeonholes are filled), so when you take the next sock you can be sure of having at least three pairs of a single colour.

If the three pairs can be any colours, then the worst case is two pairs and three odd socks and the next sock will ensure at least three pairs.