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.

• Question

  Each of seven children is holding a balloon that is either red, green, or blue. Prove that there are three children with balloons of the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Proof by Contradiction

• Question

  Given `11` numbers between `1` and `99`. Prove that there are two of them such that their difference is strictly less than `10`.

  Topics:

  Combinatorics -> Pigeonhole Principle

• Question

  The numbers `1`, `2`, `3`, ..., `9` are divided into `3` sets. Prove that there is a set where the product of the numbers is greater than or equal to `72`.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory Combinatorics -> Pigeonhole Principle Algebra -> Inequalities Proof and Example -> Proof by Contradiction

• Question

  Given `50` distinct natural numbers between `1` and `100`. It is known that no two of these numbers sum to `100`. Is it necessarily true that one of these numbers must be a perfect square?

  Topics:

  Number Theory -> Prime Numbers Arithmetic Combinatorics -> Pigeonhole Principle Combinatorics -> Matchings Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Inside a square with side length 1, `n>=101` points are marked, such that no three are collinear. A triangle is called marked if its vertices are marked points. Prove that the area of one of the marked triangles is less than `1/100`

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Geometry -> Area Calculation
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 4

• Question

  Given an infinite grid whose vertices are colored with two colors, blue and red. Prove that there exist two horizontal lines and two vertical lines such that their four intersection points are colored with the same color.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Combinatorics -> Colorings
  Sources:
  • Zebra Exercises, 2018-2019, Exercise 1 Question 1

• Toys

  Jonathan has a collection of wooden toys. Some are cubes and some are spheres, some are red and some are blue.

  It is known that there are more spheres than cubes, and it is known that there are more blue toys than red toys.

  Prove that Jonathan has a blue sphere.

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 1

• Quiz

  In a class of 25 students, a quiz was given consisting of 7 questions. Prove that at least one of the following two statements is true:

  1. There is a student who solved an odd number of questions.
  2. There is a question that was solved by an even number of students.
  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 5-6 Question 5

• The Round Table

  Around a round table are 12 chairs, with knights sitting on some of them. Arthur wants to join the meeting,
  and it turns out that no matter where he sits, someone is definitely sitting next to him.
  What is the smallest number of knights that can be around the table to ensure this is true? (not including Arthur)

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage B, Grades 3-4 Question 1

• Drawing Board

  A painter has a `10 times 10` grid. Each time, the painter chooses a row or column and paints it entirely with a color of their choice.
  If they pass over a square that has already been painted with a new color, the new color completely covers the old color,
  that is, the color of the square changes.
  What is the largest number of colors we can see on this board?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage B, Grades 5-6 Question 5