Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Presumably, "many" red socks does not mean an infinite number of red socks? – JavaMan May 11 '11 at 6:24
yes I have been thinking about the wrong question. three pairs of one color are desired – kuch nahi May 11 '11 at 6:25
By the way, an "infinite version" of the pigeonhole principle can be interpreted in terms of cardinal numbers. See (for instance) for more details. – JavaMan May 11 '11 at 6:26
@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? – kuch nahi May 11 '11 at 6:32
@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. – André Nicolas May 11 '11 at 6:58
up vote 2 down vote accepted

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

share|cite|improve this answer
you are right. the question I posted is wrong. Three pairs each of one color are desired. – kuch nahi May 11 '11 at 6:24
which i was able to solve. But I should have thought this up before doubting myself ;) – kuch nahi May 11 '11 at 6:44

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.