1999 USAMO Problems/Problem 1

Problem

Some checkers placed on an $n\times 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 $(n^{2}-2)/3$ checkers have been placed on the board.

Solution

for the proof lets look at the checkers board as a graph G, where the checkers are the vertices and the edges are every pair of checkers sharing a side.

define R as the circuit rank of G(the minimum number of edges to remove from a graph to remove all its cycles).

define $x$ as the number of checkers placed on the board.

1. from (a) for every square containing a checker there can be up to 4 distinct squares without checkers thus, $4\times x + x = 5\times x >= n^2$ (this is the most naive upper bound).

2. from (b) this graph has to be connected. which means that no square which contains a checker can share 4 sides with squares that doesn't contain a checker(because it has to share at least one side with a square that contains a checker ).

3. now it is possible to improve the upper bound. since every edge in G represents a square with a checker that shares a side with a square with another checker. the new upper bound is $5\times x -$(sum of degrees in G)$>= n^2$

4. thus, $5\times x - (2 \times x - 2 + 2\times R) >= n^2$ (see lemma below).

5. thus, $3\times x + 2 - 2\times R >= n^2$

6. thus, $x >= (n^2 - 2 + 2\times R)/3$

where $R>=0$ and is equal to 0 if G is a tree.

$clarification/lemma:$

the sum of degrees of a connected graph $G = (V,E)$ is $2 \times V -2 + 2\times R = 2\times E$

where $R$ is the circuit rank of $G$.

$proof:$

$2 \times V -2$ is the sum of ranks of the spanning tree created by decircuiting the graph $G$.

since the circuit rank of $G$ is $R$, $2\times R$ is the sum of ranks removed from $G$.

thus, $2 \times V -2 + 2\times R = 2\times E$

See Also

1999 USAMO (ProblemsResources)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png