2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Suppose that I place $n$ items into $k$ boxes..." First comment : if $n \le k$ then I can put each item into a separate box and thus I've no guarantee that one of the boxes contains more than one item. $\endgroup$ – Mauro ALLEGRANZA Dec 12 '16 at 10:05
  • $\begingroup$ Thus, we need $n > k$ for the items. If I have 5 boxes and 7 balls the two "extra" balls can go in separates boxes; thus, with 7 balls, I've no guarantee that 3 balls can go in the same box and thus the only guarantee I have is about two boxes with 2 balls each : $m=2$. $\endgroup$ – Mauro ALLEGRANZA Dec 12 '16 at 10:10
  • $\begingroup$ For sure it may happens that with 7 balls we will find 3 balls in one box (and an empty box) : it may happens, but this does not means that it necessarily happens (to be guaranteed that ...). $\endgroup$ – Mauro ALLEGRANZA Dec 12 '16 at 10:12
  • $\begingroup$ I get what you're saying. What I find appealing to think about is that "I've got no guarantee that 3 balls can go in the same box", but why is that guarantee weaker than the guarantee that "two boxes with 2 balls each"? $\endgroup$ – Garth Marenghi Dec 12 '16 at 10:55
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The bogus solution is part of the book series Art of Problem Solving. It is meant to show you how you could have done it wrong. In this case, not considering that division not always gives back an integer. Though what is made more clear by your answer is that the PHP is also applicable when not evenly distributed. I think that that is very interesting. Also, why they choose for the floor function + 1 instead of the ceiling function...? $\endgroup$ – Garth Marenghi Dec 12 '16 at 11:35
  • $\begingroup$ I see. Well, sometimes the point of view of a book does not agree with a particular reader's intuition, and then it's just confusing. Also, why anyone would choose floor((n-1)/k)+1 over ceiling(n/k) is beyond me. $\endgroup$ – Evangelos Bampas Dec 12 '16 at 11:45
  • $\begingroup$ With the placement P, in case of 7 balls and 5 boxes, fullest(P) would be {2, 3}, since we can put 5 balls in 5 separate boxes, and the two leftover balls could be either distributed over 2 boxes (so that two boxes have 2 items in them), or put into one box (so that one box has 3 items in them). Then m = min({2, 3})? Do i have that correct? $\endgroup$ – Garth Marenghi Dec 12 '16 at 11:55
  • $\begingroup$ fullest(P) is just a number, not a set. I'll try to add an example to the answer in order to clarify. $\endgroup$ – Evangelos Bampas Dec 12 '16 at 12:27
  • $\begingroup$ Awesome, thanks! $\endgroup$ – Garth Marenghi Dec 12 '16 at 12:52
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That was not even all of the presented solution. There's a couple of algebraic manipulations and inequalities also in there, but I did not dare to go there yet. $\endgroup$ – Garth Marenghi Dec 12 '16 at 11:36

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.