# Pigeon hole principle proof writing

I'm currentely discussing pigeon hole principle (simple and generalised) in class. However, when solving problems, I get the idea, but I never know the proper way to write it, I always feel like I'm either writing too much or not enough. Here is an example of a very simple problem and 2 ways I wrote the proof and if you could comment and give me tips it would be very appreciated!!

Problem

A man in a dark room has a box with 12 brown and 12 black socks. How many times, if picking one at a time, does the man have to pick a sock to have 2 of the same color?

(Here I think of the two colors as the "boxes" and the picks as the "objects". Since there's k+1 objects (or picks) and k boxes (or type of socks) then the pigeon hole principle apply)

Solution 1

There are $2$ different type of socks the man can pick . By the pigeon hole, principle if the man picks $3$ socks, it is garanteed that he will have $2$ socks of the same color $\blacksquare$.

Solution 2

The generalised pigeon hole principle says that, for $N,k \in \Bbb{Z}$, if $N$ objects are placed in $k$ boxes, then at least $1$ boxe will have $\lceil{\frac{N}{k}}\rceil$ objects.

Let $k = 2$ be the the colors of the socks and $N$ be the number of picks

The minimum amount of picks the man has to do to garantee he will pick $2$ socks of the same color is the smalles integer such that $\lceil{\frac{N}{2}}\rceil = 2$

Therefore, we need the minimum integer $N$ picks such that $1\lt \lceil{\frac{N}{2}}\rceil \le 2 \Rightarrow N = 3$ since $3 = 1*2 + 1$

So, by the generalised pigeon principle, to guarantee the man picks 2 socks of the same color, he has to pick 3 socks$\blacksquare$.

Conlcusion

I know the problem is very simple but I really need to know how to write that kind of proof in a way such that I say enough but not too much. I mean I feel like in the first solution I'm not convincing and in the second one I blabla for no reasons..

As usual, thank you everyone for your help!!!!

• I vote for Solution 1 – Bram28 Mar 21 '18 at 19:07
• Solution 1 for sure (though it may depend on your instructor; you might want to ask them) – E-A Mar 21 '18 at 19:12
• For a different view on this principle, see Edsger W. Dijkstra's EWD980 and EWD1094. – Marnix Klooster Mar 26 '18 at 20:37

In most contexts, Solution 1 is a perfectly fine amount of detail and Solution 2 is way more than is necessary. There is one important way that both solutions are incomplete, though: you've explained why picking $3$ socks guarantees $2$ of the same color, but you haven't explained why no smaller number guarantees $2$ of the same color. To have a completely thorough proof, you need to also mention how it is possible to choose $2$ socks which are of different colors.
(This observation is obvious enough that in many contexts it would be fine not to write it out explicitly, though. Note that in Solution 2 you implicitly made a more general claim when you asserted that the minimum number of picks to guarantee two socks of the same color is the smallest $N$ such that $\lceil{\frac{N}{2}}\rceil = 2$. This does not follow from the pigeonhole principle alone, since you are also claiming that no smaller $N$ can work.)