2
$\begingroup$

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

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

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

$\endgroup$

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.