1999 USAMO Problems/Problem 1
Contents
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 1
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,
Solution 2
Call a square of the checkerboard “good” if it either has a checker on it or shares a side with a square with a checker on it.
Say there are checkers on the board, sitting on squares
. We can assume WLOG that
is ordered in such a way that if
, then
shares a side with
at least one of
. (If such an ordering were impossible, then some
wouldn’t be reachable from
, violating condition (b)).
Now imagine removing all the checkers and then putting them back onto squares in that order, counting the number of good squares after each
step. When we put a checker on
, we increase the number of good squares
by at most 5: the square the checker goes on becomes good, and each square it
shares a side with (at most 4) becomes good. When we put a checker onto
,
where
, we increase the number of good squares by at most
:
is
already good, and one of its at most
neighbors is already good.
So the total number of good squares when we’ve put back every checker is at most . Since we know all of the
squares are good,
, and therefore
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.