Difference between revisions of "1999 USAMO Problems/Problem 1"
m (→Solution) |
(→Solution 2) |
||
(6 intermediate revisions by the same user not shown) | |||
Line 8: | Line 8: | ||
Prove that at least <math>(n^{2}-2)/3</math> checkers have been placed on the board. | Prove that at least <math>(n^{2}-2)/3</math> checkers have been placed on the board. | ||
− | == Solution == | + | == Solution 1 == |
For the proof let's look at the checkers board as a graph <math>G</math>, where the checkers are the vertices and the edges are every pair of checkers sharing a side. | For the proof let's look at the checkers board as a graph <math>G</math>, where the checkers are the vertices and the edges are every pair of checkers sharing a side. | ||
Line 30: | Line 30: | ||
<math>\textit{Proof.}</math> <math>2 \times V -2</math> is the sum of ranks of the spanning tree created by decircuiting the graph <math>G</math>. Since the circuit rank of <math>G</math> is <math>R</math>, <math>2R</math> is the sum of ranks removed from <math>G</math>. Thus, <math>2V -2 + 2R = 2 E.</math> <math>\blacksquare</math> | <math>\textit{Proof.}</math> <math>2 \times V -2</math> is the sum of ranks of the spanning tree created by decircuiting the graph <math>G</math>. Since the circuit rank of <math>G</math> is <math>R</math>, <math>2R</math> is the sum of ranks removed from <math>G</math>. Thus, <math>2V -2 + 2R = 2 E.</math> <math>\blacksquare</math> | ||
+ | |||
+ | == 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 <math>k</math> checkers on the board, sitting on squares <math>s_1, \ldots, s_k</math>. We can assume WLOG that <math>s_1, \ldots, s_k</math> is ordered in such a way that if <math>1 \leq i \leq k</math>, then <math>s_i</math> shares a side with at least one of <math>s_1, \ldots, s_{i - 1}</math>. (If such an ordering were impossible, then there would be an <math>s_i</math> which isn’t connected to <math>s_1</math> 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 <math>s_1, | ||
+ | \ldots, s_k</math> in that order, counting the number of good squares after each | ||
+ | step. When we put a checker on <math>s_1</math>, we increase the number of good squares | ||
+ | by at most 5: the square <math>s_1</math> becomes good, and each square it | ||
+ | shares a side with (at most 4) becomes good. When we put a checker onto <math>s_i</math>, | ||
+ | where <math>i > 1</math>, we increase the number of good squares by at most <math>3</math>, since <math>s_i</math> is | ||
+ | already good, and at least <math>1</math> of its at most <math>4</math> neighbors already has a checker on it. | ||
+ | |||
+ | So the total number of good squares when we’ve put back every checker is at most <math>5 + 3(k - 1) = 3k + 2</math>. In order to satisfy condition (a), we have to make each of the <math>n^2</math> squares good. In other words, we need <math>3k + 2 \geq n^2</math>, or <cmath>k \geq \frac{n^2 - 2}{3}.</cmath> | ||
== See Also == | == See Also == |
Latest revision as of 05:23, 13 May 2023
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 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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.