I think this might be a stupid doubt but I still would want this to be clarified. Here is the following question from the AOPS website for pigeonhole principle.

If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, how many socks must the Martian pull out of the drawer to guarantee he has a pair?

I am denoting the pairs as follows:- $$(Red, Left) - RL\\(Red, Right) -RR\\(Blue,Left)-BL\\(Blue, Right)-BR\\(Yellow, Left)-YL\\(Yellow, Right)-YR\\(Black, Left)-BlL\\(Black, Right)-BlR\\$$

The answer to the above question is 5 and here is the following answer:-

The Martian must pull 5 socks out of the drawer to guarantee he has a pair. In this case the pigeons are the socks he pulls out and the holes are the colors. Thus, if he pulls out 5 socks, the Pigeonhole Principle states that some two of them have the same color. Also, note that it is possible to pull out 4 socks without obtaining a pair.

However, I am not sure about that answer. This is because we could have $5RL$ socks too, or there might be many possibilities such that one could guarantee you cannot have a pair. For example, $5RL$, $4RL 1BL$ and so on and so forth.

Ideally if we have $n$ socks for each of the 8 combinations mentioned above, then the Martian should pick out $4n+1$ socks inorder to guarantee that he will have a pair. I hope I am right about what I am thinking here.

  • $\begingroup$ A pair of socks in this sense means a pair of socks, no further questions. $\endgroup$ – Rohan Dec 28 '17 at 13:43
  • $\begingroup$ I think your confusion is about whether you consider the right socks to be different from the left socks or not. If it was gloves, it would be obvious, but I think socks are usually treated as interchangeable. (At least in word problems; in real life YMMV...) $\endgroup$ – user491874 Dec 28 '17 at 13:45
  • $\begingroup$ yes, you are right. But, it also says that the person is a Martian. You can't assume that the socks may be different or the same. The assumption may vary. Seems kinda stupid. :) $\endgroup$ – Palash Ahuja Dec 28 '17 at 13:52

I imagine the given solution is assuming left and right socks are indistinguishable. If left and right socks are distinguishable, then your math is correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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