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 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 there would be an which isn’t connected to by a sequence of squares with checkers on them, violating condition (b).)

Now imagine removing all the checkers and then putting them back onto the 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 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 , since is already good, and at least of its at most neighbors already has a checker on it.

So the total number of good squares when we’ve put back every checker is at most . In order to satisfy condition (a), we have to make each of the squares good. In other words, we need , or

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

These problems are copyrighted © by the Mathematical Association of America.