Drichlet Box

Context: Pigeonhole Principle Wikipedia Article.

A function that maps the (holesCount, pigeonsCount, pigeonIndex) 3-tuple to the corresponding holeIndex, in constant time.

Explanation

Given a wooden structure with holesCount pigeonholes and pigeonsCount pigeons, the drichlet-box function returns the zero-based hole index, holeIndex, in which a pigeon indicated by the zero-based integer pigeonIndex should go, so that the following holds:

1. There are at least floor(pigeonsCount/holesCount) pigeons in a hole (small hole).
2. There are at most floor(pigeonsCount/holesCount) pigeons in a hole (big hole).
3. drichlet-box is an increasing function in regards to its pigeonIndex argument.
4. The big holes are the first ones. In other words, if i is an index of a big hole and j is an index of a small hole, i < j.