I understand the proof of generalised pigeonhole principle but there is a result which follows from it is not making sense to me.
The text is taken from Discrete Mathematics by Kenneth Rosen :
A common type of problem asks for the minimum number of objects such
that at least $r$ of these objects must be in one of $k$ boxes when these
objects are distributed among the boxes. When we have $N$ objects, the
generalized pigeonhole principle tells us there must be at least $r$
objects in one of the boxes as long as $\lceil N/k \rceil \geq r$. The
smallest integer $N$ with $N/k > r − 1$, namely, $N = k(r − 1) +
> 1$, is the smallest integer satisfying the inequality $\lceil N/k \rceil \geq r$. Could a smaller value of $N$ suffice? The answer is no, because if
we had $k(r − 1)$ objects, we could put $r − 1$ of them in each of the $k$ boxes and no box would have at least $r$ objects.When thinking about problems of this type, it is useful to consider
how you can avoid having at least $r$ objects in one of the boxes as you
add successive objects. To avoid adding a $r$th object to any box, you
eventually end up with r − 1 objects in each box. There is no way to
add the next object without putting an $r$th object in that box.
I don't understand what is the purpose of $N/k > r − 1$ and how it is being used in $N = k(r − 1) +1$.
I get the idea (if I am right) that they are trying to prove what is the minimum number objects in a set of boxes if there is at least one box contains more than one object.
Best Answer
The generalised pidgeonhole principle answers the question of how many objects are required to make sure that the fullest box always contains at least $r$ objects.
If $N/k = r-1$, then $N = k(r-1)$ and all of the boxes can be filled with $r-1$ objects and hence $N$ is not large enough. That is why $N/k > r-1$, and thus $N > k(r-1)$. The smallest integer $N$ satisfying $N > k(r-1)$ is $k(r-1) + 1$.