There are (2n - 1) rooks on a (2n - 1)×(2n - 1) board placed so that none of them threatens another. Prove that any n×n square contains at least one rook.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

There are (2n - 1) rooks on a (2n - 1)×(2n - 1) board placed so that none of them threatens another. Prove that any n×n square contains at least one rook.

Solution

Assuming an n×n square is void of the rooks, there remain n - 1 vertical and n - 1 horizontal lines to house (2n - 1) rooks. But each of these 2n - 2 lines may carry only one rook. By the Pigeonhole principle this is impossible.

(This is Problem 11.5 from the 1993-1994 St Petersburg Regional Mathematical Olympiad, grade 11.)


Related material
Read more...

  • Three Colors on a Chessboard
  • Consequences of Getting More Than a Half
  • Remainder Multiples of 1997
  • Intersecting Subsets
  • Over-The-Counter Pigeonhole
  • Women in a theatre: Pigeonhole Principle
  • Pigeonhole Among Friends
  • Not Exceeding 24

    • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    72104449