TOPICS
Search

Dirichlet's Box Principle

A.k.a. the pigeonhole principle. Given n boxes and m>n objects, at least one box must contain more than one object. This statement has important applications in number theory and was first stated by Dirichlet in 1834.

In general, if n objects are placed into k boxes, then there exists at least one box containing at least [n/k] objects, where [x] is the ceiling function.

See also

Fubini Principle

Explore with Wolfram|Alpha

References

Bogomolny, A. "Pigeonhole Principle." http://www.cut-the-knot.org/do_you_know/pigeon.shtml.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 38, 1985.Nagell, T. Introduction to Number Theory. New York: Wiley, p. 38, 1951.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 161, 1993.

Referenced on Wolfram|Alpha

Dirichlet's Box Principle

Cite this as:

Weisstein, Eric W. "Dirichlet's Box Principle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DirichletsBoxPrinciple.html

Subject classifications