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
    @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
    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.