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.

• Hunter in the Enchanted Forest

  In the enchanted forest lives a tribe of 150 people. Every day, the tribe members try to organize themselves to go hunting together,
  and each day, each person participates or does not participate according to their choice. Prove that during one week, there will certainly be two people who arrive on exactly the same days.
  Note: Even in the enchanted forest, a week has 7 days.

  Topics:

  Combinatorics -> Pigeonhole Principle
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Final, Grades 5-6 Question 4

• Colorful Street

  Along the street are 16 houses, in red, blue, and green. There is at least one house of each color. No two adjacent houses are of the same color.
  Between any two blue houses there is a red house. Between any two green houses there is a blue house and a red house.
  What is the largest possible number of green houses?
  Note: The street is straight, all houses are located on one side of the street.

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 3-4 Question 6

• Colorful Street 2

  There are 15 houses along the street, colored red, blue, and green. There is at least one house of each color.
  Between any two blue houses there is a red house. Between any two green houses there is a blue house.
  What is the largest possible number of green houses?
  Note: The street is straight, and all houses are located on one side of the street.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 5-6 Question 5
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 7-8 Question 6

• A TENNIS TOURNAMENT

  Four married couples played a "mixed double" tennis tournament, a man and a lady always playing against a man and a lady. But no person ever played with or against any other person more than once. Can you show how they all could have played together in the two courts on three successive days? This is a little puzzle of a quite practical kind, and it is just perplexing enough to be interesting.
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Double Counting
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 266

• THE THIRTY-SIX LETTER BLOCKS

  The illustration represents a box containing thirty-six letter-blocks. The puzzle is to rearrange these blocks so that no A shall be in a line vertically, horizontally, or diagonally with another A, no B with another B, no C with another C, and so on. You will find it impossible to get all the letters into the box under these conditions, but the point is to place as many as possible. Of course no letters other than those shown may be used.
  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 305

• THE CROWDED CHESSBOARD

  The puzzle is to rearrange the fifty-one pieces on the chessboard so that no queen shall attack another queen, no rook attack another rook, no bishop attack another bishop, and no knight attack another knight. No notice is to be taken of the intervention of pieces of another type from that under consideration—that is, two queens will be considered to attack one another although there may be, say, a rook, a bishop, and a knight between them. And so with the rooks and bishops. It is not difficult to dispose of each type of piece separately; the difficulty comes in when you have to find room for all the arrangements on the board simultaneously.
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Amusements in Mathematics, Henry Ernest Dudeney Question 306