An nxn Checkboard
Source: USAMO 1999 Problem 1
October 3, 2005
inductioncombinatorics proposedcombinatorics
Problem Statement
Some checkers placed on an checkerboard satisfy the following conditions:
(a) every square that does not contain a checker shares a side with one that does;
(b) given any pair of squares that contain checkers, there is a sequence of squares containing checkers, starting and ending with the given squares, such that every two consecutive squares of the sequence share a side.
Prove that at least checkers have been placed on the board.