If $m$ objects are distributed among $n$ containers, then at least one container holds atleast $1 + \lfloor\frac {m − 1}{n}\rfloor$ objects.

Question

There are many ways that I can prove this. I want to prove using contradiction. The issue is that I have trouble negating the consequent.

I am trying to contradict no container holds at most $1 + \lfloor\frac {m − 1}{n}\rfloor$ objects. This is really weird to interpret. It seems to say a container can hold more than $1 + \lfloor\frac {m − 1}{n}\rfloor$ objects. This is true because a container can hold m objects. This statement seems to be one that should not be contradicted.

Second thought was that each container holds at most $1 + \lfloor\frac {m − 1}{n}\rfloor$ objects. This is easy to contradict because a container can have m objects. I do not think this actually implies the original implication was true, though.

I do not want anyone to prove for me. I want to know if I am contradicting correct thing.

Answer 1

You want the negation of the statement that

$$\text{at least one container holds at least }1+\left\lfloor\frac{m-1}n\right\rfloor\text{ objects}\;.$$

That negation is:

$$\text{no container holds at least }1+\left\lfloor\frac{m-1}n\right\rfloor\text{ objects}\;,$$

i.e.,

$$\text{no container holds }1+\left\lfloor\frac{m-1}n\right\rfloor\text{ or more objects.}$$

This is turn is equivalent to:

$$\text{every container holds fewer than }1+\left\lfloor\frac{m-1}n\right\rfloor\text{ objects.}$$

In other words, if some container holds $k$ objects, then $k<1+\left\lfloor\frac{m-1}n\right\rfloor$. And since the number of objects in a container must be an integer, this means that $k\le\left\lfloor\frac{m-1}n\right\rfloor$. Thus, our negation can be restated as follows:

$$\text{every container holds at most }\left\lfloor\frac{m-1}n\right\rfloor\text{ objects.}$$

Stated in more detail, it is:

$$\text{if a container holds }k\text{ objects, then }k\le\left\lfloor\frac{m-1}n\right\rfloor\;.$$

Answer 2

We know that $1+\left\lfloor \frac{m-1}{n}\right\rfloor $ is a positive integer. So, the greatest integer less than $1+\left\lfloor \frac{m-1}{n}\right\rfloor $ is $\left\lfloor \frac{m-1}{n}\right\rfloor $. If you're trying to prove that at least one container has at least $1+\left\lfloor \frac{m-1}{n}\right\rfloor $ objects, show that if all $n$ containers all have $\left\lfloor \frac{m-1}{n}\right\rfloor $ objects or fewer, that the total number of objects will definitely be less than $m$, i.e, $$n\left\lfloor \frac{m-1}{n}\right\rfloor<m.$$