Raising the bar

Boxes-and-balls principle

This is my response to Section 4.6 "The pigeonhole principle" of the study guide "Abstract mathematics" by M. Anthony (MT2116, 2790116), 2011.

For the name, I prefer "Boxes-and-balls principle".

Statement. There are some boxes and balls. The balls are randomly thrown into boxes. 1) If the number of balls $latex m$ is larger than the number of boxes $latex n$, then at least one of the boxes should contain more than one ball. 2) If we know that all balls have been put into boxes and no box contains more than one ball, then it must be that $latex m\leq n.$

Proof by contradiction. 1) Assume that no box contains more than one ball. Let us number the boxes: $latex B_{1},...,B_{n}.$ Let us count the number of balls in each box: $latex m_{1}\leq 1$ in box $latex B_{1},\ ...,$ $latex m_{n}\leq 1$ in box $latex B_{n}. $ Obviously, then the total number of balls does not exceed $latex n:  m=m_{1}+...+m_{n}\leq n.$ This contradicts the statement condition that $latex m>n$ and the contradiction proves that our assumption was wrong.

2) If we assume that $latex m>n,$ then by part 1) at least one box should contain more than one ball, contradicting the condition in part 2).

Compare this proof to the cumbersome proof using induction in the guide on pp. 62-63.

There are typos in the proof of Theorem 4.6, so I provide the correct and slightly reformulated version.

Theorem 4.6. In a room there are $latex n\geq 2$ people. Then there are at least two people with the same number of friends.

Proof. Let $latex P$ be the set of people in the room and let $latex f(p)$ denote the number of friends of person $latex p\in P.$ For the purposes of this proof, we assume that no person is considered a friend of him/herself. (The opposite definition, that every person is his/her own friend, is handled with a small change in the argument). From this definition it follows that $latex 0\leq f\left(p\right) \leq n-1$ for any $latex p.$ Now consider two cases:

1) If some $latex p_{1}$ has every person in the room as a friend, then $latex f\left(p_{1}\right) =n-1$ and there are no people who don't have any friends, so that $latex f\left( p\right) >0$ for any other person.

2) Suppose that some $latex p_{2}$ does not have any friends, that is, $latex f\left(p_{2}\right) =0$. Then for any other person $latex p,$ the number of friends cannot be larger than $latex n-2$ (because $latex p_{2}$ and self are excluded).

Thus, the situations a) exists $latex p_{1}$ such that $latex f\left( p_{1}\right) =n-1$ and b) exists $latex p_{2}$ such that $latex f\left( p_{2}\right) =0$ cannot occur at the same time. Now let us group people by the number of friends they have: we write $latex p\in P_{k}$ if $latex f\left( p\right) =k.$ As we just established, the conditions $latex k=0$ and $latex k=n-1$ are mutually exclusive. Hence, the number of possible values of $latex k$ is necessarily a subset of either $latex \left\{1,...,n-1\right\} $ or $latex \left\{ 0,1,...,n-2\right\} .$ Treating the sets $latex P_{k}$ as boxes (their number is $latex n-1$) and the people as balls, by the boxes-and-balls principle at least two people should be in the same box and have an equal number of friends.