Not quite understanding parts of Pigeon Hole Principle Generalization

Question

Q

Suppose that I place n items into k boxes. What is the largest number m such that I can be guaranteed that one of the boxes contains at least m items?

First off, I'm not completely understanding the question. "The largest number m such that I can be guaranteed that one of the boxes contains at least m items?" The largest number m? Why the largest? If you have at least m items, how can it be the largest?

A

Bogus solution: we can put $\frac{n - 1}{k}$ balls into each of the k boxes. This accounts for $k (\frac{n - 1}{k}) = n - 1$ of the balls. There is 1 ball left over, which must go in some box, and thus some box must contain at least $\frac{n - 1}{k} + 1$ balls. Seems reasonable, and works with n = 25 and k = 6. So why is this not quite correct?

The problem is that $\frac{n - 1}{k}$ might not be an integer. The best we can do in out initial step is to put $\lfloor{\frac{n - 1}{k}}\rfloor$ balls in each box. Then our leftover ball(s) ensure that at least on box will have $\lfloor{\frac{n - 1}{k}}\rfloor + 1$ balls.

What I'm not understanding here, is why $n - 1$ is used in $\lfloor{\frac{n - 1}{k}}\rfloor$. I can see that it doesn't always work with n or $n - 2$, but what is it about $n - 1$ that makes it work? Is it so that you can say that at least one box has at least m balls?

Also, let's say that I have 7 balls and 5 boxes. The pigeonhole principle works when you put each ball in a box, not when you put all balls in one box (or am I wrong?) My question is, after 5 balls have been put into 5 boxes, and we have two balls left, do the two leftover balls also still need to be distributed, or can I put the two balls into one box?

Because the generalized Pigeonhole Prinicple states that: if we place n balls into k boxes, then at least one box must contain at least $\lfloor \frac{n - 1}{k} \rfloor + 1$ balls.

In the case of 7 balls and 5 boxes, this seems to imply to me that the two leftover balls can be deposited in one box. If we place 7 balls into 5 boxes, then at least one box must contain at least $\lfloor \frac{7 - 1}{5} \rfloor + 1 = 2$ balls. This statement would therefore also be true if one box contains 3 balls.

Answer 1

The (strong) pigeonhole principle says that, whatever way I choose to distribute $n$ items into $k$ boxes, at least one box will have at least $\lceil \frac{n}{k} \rceil$ items. (note that $\lceil \frac{n}{k} \rceil = \lfloor \frac{n-1}{k} \rfloor +1$)

First of all, in general, you can put the items into the boxes any way you like. For example, if you put all of the items into one box, then you will have one box with $n$ items. This agrees with what is predicted by the pigeonhole principle, which gives the more modest bound of at least one box with at least $\lceil \frac{n}{k} \rceil$ items.

However, the way to "test" the principle, i.e. to have a placement of items in which the box with the most items contains as few items as possible, is to distribute the items as evenly as possible into the boxes.

Second, I don't see the point of this convoluted "bogus solution" that you present. The way I like to think about it is the following: Suppose that I distribute all $n$ items into the $k$ boxes in an arbitrary manner. If, in the end, every box contains strictly less than $\lceil \frac{n}{k} \rceil$ items (therefore, at most $\lceil \frac{n}{k} \rceil -1$ items), then the total number of items would be at most $k\cdot(\lceil\frac{n}{k}\rceil-1)$, which is, as can be easily verified, strictly smaller than $n$. This is a contradiction because I assumed that I distributed all items. Therefore, for every placement, there is at least one box with at least $\lceil \frac{n}{k} \rceil$ items.

Finally, the question, as stated, does make sense once you're used to seeing questions phrased like this. An alternative way to phrase it would be: For every placement $P$, let $\mathrm{fullest}(P)$ be the number of items in the fullest box. What is the largest $m$ such that $$\min_P \mathrm{fullest}(P) \geq m \enspace,$$ where $P$ ranges over all possible placements of $n$ items into $k$ boxes?

Example: Let us represent placements as lists of numbers, indicating how many items are in each box. If $n=7$ items and $k=5$ boxes, then a possible placement is $P_1=(7,0,0,0,0)$, another possible placement is $P_2=(1,0,4,1,0)$, and yet another possible placement is $P_3=(2,1,2,1,1)$. Now, using the notation above, $\mathrm{fullest}(P_1)=7$, $\mathrm{fullest}(P_2)=4$, and $\mathrm{fullest}(P_3)=2$.

There are many other possible placements, but the pigeonhole principle says that however long you try, you will never find a placement whose "fullest" value is strictly less than $2=\lceil\frac{7}{5}\rceil$. In other words, if $P$ is any placement of $7$ items into $5$ boxes, then the pigeonhole principle guarantees that $\mathrm{fullest}(P) \geq 2 = \lceil\frac{7}{5}\rceil$.

Answer 2

To be honest I find that the presented solution to problem doesn't really make a lot of sense;

Hopefully this proof sounds more reasonable to you:

Let's suppose $n\ge 1$. You want to put these $n$ balls into $k$ holes. The problem is asking the biggest number of balls that at least one hole contains no matter which way you choose to distribute the balls.

---

Lemma: Now, suppose that there is an integer $s\ge 0$ such that $n\ge sk+1$ (we know at least one such $s$ exists, namely $0$). We claim that, no matter the way you distribute the balls, at least one hole must contain more than $s$ balls.

Proof: Suppose we could distribute the balls so that every hole contains at most $s$ balls. Then this would mean $n\le sk$ since each hole contain at most $s$ balls and there are $k$ holes, contradicting $n\ge sk+1$.

Note that this proof is essentially a rather formalised version of intuitive proof; if you have $n\ge sk+1$ and try to put at most $s$ balls into each hole, in the end you will have $k$ holes filled with $s$ balls in each of them but you will still have some more balls to put into them, so at least one of the holes contain more than $s$ balls.

---

Now observe that, since $n$ is fixed natural number, then the set $S=\{s\ge 0:n\ge sk+1\}$ is non empty ($0\in S$) and bounded above. Since $S$ is finite, then $m=\max_{s\in S} s$ exists, and is a maximum integer such that $$n\ge mk+1\implies \frac{n-1}{k}\ge m$$

That is, $m=\left\lfloor\frac{n-1}{k}\right\rfloor$.

But from our earlier lemma, $m$ is the maximal number such that no matter how we distribute balls, at least one hole contains more than $m$ balls. That is, $m$ is maximal number of balls such that one of the holes contain at least $m+1$ balls.

So answer to original question is $$m+1=\left\lfloor\frac{n-1}{k}\right\rfloor+1$$