Math 2.0

Combinatorics Theorem

Generalized pigeonhole principle

Builds on Cardinality of a finite setPigeonhole principle

Statement

Let AA and BB be finite sets, let f:A→Bf : A \to B be a function, and let nn be a natural number. Assume that ∣B∣⋅n<∣A∣|B| \cdot n < |A|. Then there is an element b∈Bb \in B whose fibre f−1(b)={a∈A:f(a)=b}f^{-1}(b) = \{a \in A : f(a) = b\} has more than nn elements.

Remarks

For n=1n = 1 this is the pigeonhole principle. An equivalent form: if NN objects go into kk boxes, some box has at least ⌈N/k⌉\lceil N / k \rceil objects. Example: among 2525 people, at least 33 share a birth month, because 12⋅2<2512 \cdot 2 < 25.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Cardinality of a finite set, definition, no evidence levelCardinality of a fini…definitionPigeonhole principle, statement, no evidence levelPigeonhole principlestatementGeneralized pigeonhole principle, statement, no evidence levelGeneralized pigeonhol…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Cardinality of a finite set definition
  2. Pigeonhole principle statement
  3. Generalized pigeonhole principle statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Pigeonhole_principle, Strong form
About this page
Tag0BY7GN3449
URIm2://0BY7GN3449
Kindstatement, theorem
WritingW0 stub
MSC05A05
StatusThis copy of the site has no build data. Run m2 status 0BY7GN3449.
UsesCardinality of a finite set, Pigeonhole principle

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by