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

  A square is divided into several convex polygons (more than `1`), each of which has a different number of sides. Prove that among these polygons there is a triangle.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Geometry -> Plane Geometry -> Triangles Proof and Example -> Proof by Contradiction Geometry -> Solid Geometry / Geometry in Space -> Polyhedra Minimum and Maximum Problems / Optimization Problems

• Question

  A plane is colored with two colors (that is, every point on the plane is colored with one of these two colors). Prove that there exist two points on the plane at a distance of `1` such that they are both the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Triangles Proof and Example -> Constructing an Example / Counterexample Proof and Example -> Proof by Contradiction

• Question

  In the plane, a point and `12` lines passing through it are given. Prove that there are two of these lines such that the angle between them is less than `17^@`.

  Topics:

  Combinatorics -> Pigeonhole Principle Geometry -> Plane Geometry -> Angle Calculation

• Question

  Given `12` intersecting lines in the plane. Prove that there exist two of these lines such that the angle between them is less than `17^@`.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Geometry -> Plane Geometry -> Angle Calculation Geometry -> Plane Geometry -> Plane Transformations -> Congruence Transformations (Isometries) -> Parallel Translation / Translation

• Balls in a Bag

  In a bag, there are `70` identical balls of different colors: `20` blue, `20` red, `20` yellow, and the rest are black and white. What is the minimum number of balls that must be drawn from the bag without looking, to ensure that we have `10` balls of the same color?

  Topics:

  Combinatorics -> Pigeonhole Principle

• The King and the Corrupt Ministers

  The king of the magical land has `100` ministers. It is known that among any `10` ministers we choose, there is at least one corrupt minister. What is the minimum possible number of corrupt ministers in the magical land?

  Topics:

  Combinatorics -> Pigeonhole Principle Minimum and Maximum Problems / Optimization Problems

• Question

  A bouquet is composed of `7` roses, white and red (both colors are present). It is known that out of every two roses, one is necessarily white. How many white roses and how many red roses are in the bouquet?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Question

  Can you divide `44` balls into `9` piles, each containing a different number of balls?

  Topics:

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

• Question

  What is the maximum number of chess kings that can be placed on an `8xx8` board such that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry

• Question

  What is the maximum number of rooks that can be placed on an `8xx8` board so that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems