Some checkers placed on an n×n 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 (n2−2)/3 checkers have been placed on the board. inductioncombinatorics proposedcombinatorics