Difference between revisions of "1999 USAMO Problems/Problem 1"
(submit) |
|||
Line 47: | Line 47: | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 13:35, 4 July 2013
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.