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.)


[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]