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 let's look at the checkers board as a graph , where the checkers are the vertices and the edges are every pair of checkers sharing a side.
Define as the circuit rank of (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
4. Thus, (see lemma below).
5. Thus,
6. Thus, where and is equal to 0 if 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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.