Combinatorics, Pigeonhole Principle

The Pigeonhole Principle states that if `n` items are put into `m` containers, with `n > m`, then at least one container must contain more than one item. Questions involve applying this principle (and its generalized forms) to prove existence or establish bounds in various scenarios.

• Apples and Pears

  There is a basket containing `30` fruits. It is known that among any `12` fruits we take from the basket, there is necessarily at least one apple, and among any `20` fruits there is necessarily one pear. How many apples and how many pears are there in the basket?

  Topics:

  Combinatorics -> Pigeonhole Principle Algebra -> Inequalities Logic -> Reasoning / Logic
  Sources:
  • problems.ru web site

• Question

  The numbers `1`, `2`, `3`, ..., `8` are written on the vertices of a cube. Prove that there exists an edge of the cube such that the difference between the numbers at its endpoints is at least `3`.

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction

• Stack of Papers

  Several identical rectangular sheets of paper lie on a table. It is known that the top sheet covers more than half the area of every other sheet. Is it necessarily possible to stick a pin into the table that will go through all these sheets?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Area Calculation Geometry -> Plane Geometry -> Symmetry

• Question

  Prove that every polyhedron has at least two faces with the same number of edges.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Geometry -> Solid Geometry / Geometry in Space -> Polyhedra

• Knights of the Round Table

  Around a round table sit 12 knights, each of whom is either an elf or a dwarf. It is known that the number of elves is greater than the number of dwarves. Prove that there are two elves who sit opposite each other.

  Will this continue to be true if the total number of knights is 120?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction

• Question

  Prove that among five integers, it is possible to choose two whose difference is divisible by `4`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle Number Theory -> Division -> Parity (Even/Odd) Arithmetic -> Division with Remainder

• Question

  a. Prove that among `11` natural numbers, it is always possible to choose two such that their units digit is the same.

  b. Prove that among `11` natural numbers, it is always possible to choose two such that their difference is divisible by `10`.

  Topics:

  Combinatorics -> Pigeonhole Principle Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 5 and 25

• Question

  A total of `21` children have `200` nuts. Prove that there exist two children who have the same number of nuts.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction Minimum and Maximum Problems / Optimization Problems

• Question

  There are `30` students in a class. During a test, Pinchas made `13` mistakes, and the rest made fewer mistakes. Prove that there are three students who made the same number of mistakes.

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Minimum and Maximum Problems / Optimization Problems

• Question

  The numbers from `1` to `2n` are written in a row in some order. Add to each number the index of the position it stands on. Prove that among the `2n` sums we obtained, there are two whose difference is divisible by `2n`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction