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 box contains `14` black socks and `14` white socks. Apart from color, all socks in the box are identical. Danny wants to take a pair of socks from the box without looking inside. How many socks does he need to take out to:

  A. Certainly have any pair of socks,

  B. Certainly have a pair of black socks?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  An `N×N` table is filled with numbers such that all rows are distinct (differing in at least one position). Prove that it is possible to delete a column such that in the remaining table all rows are also distinct.
  (a) Hint

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 2

• Question

  In space, there are 30 non-degenerate vectors. Prove that there are at least 2 such that the angle between them is no greater than 45 degrees. 
  A. Tulpigo

  Topics:

  Geometry -> Trigonometry Geometry -> Spherical Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Angle Calculation Geometry -> Vectors
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 4

• Question

  In a company, there are `30` employees. The youngest is `20` years old, and the oldest is `45` years old. Is it necessarily true that there are people in this company who are the same age?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  In a school, there are `400` students. Prove that there exist two students who celebrate their birthday on the same date of the year.

  Topics:

  Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  Someone made `15` point-like holes in a carpet that is `4xx4` meters in size. Is it always possible to cut out a rug of size `1xx1` meter from the original carpet such that it has no holes?

  Show hint

  Log in here to receive the hint
  Topics:

  Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry
  Sources:
  • problems.ru web site

• Question

  Can you fill a table of size `5xx5` with

  a. Integers,

  b. Real numbers,

   such that the sum of each row is even, and the sum of each column is odd?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Double Counting Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  In a magical country, there are coins worth `1`, `2`, `3` and `5` liras. Yossi has `25` coins from the magical country.

  Must there necessarily be `7` coins of the same value among these coins?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • problems.ru web site

• Question

  In a class of `38` students, prove that there are four students who celebrate their birthday in the same month.

  Topics:

  Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site

• Question

  Prove that there exist two powers of `2` such that their difference is divisible by `2017`.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Pigeonhole Principle
  Sources:
  • problems.ru web site