1999 USAMO Problems/Problem 1
Problem
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.
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 
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, 
(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 
(sum of degrees in G)
4. thus, 
(see lemma below).
5. thus, 
6. thus, 
where 
and is equal to 0 if G is a tree.
the sum of degrees of a connected graph 
is 
where 
is the circuit rank of 
.
is the sum of ranks of the spanning tree created by decircuiting the graph .
since the circuit rank of is , 
is the sum of ranks removed from .
thus,
See Also
| 1999 USAMO (Problems • Resources) | ||
| Preceded by First Question |
Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
