Difference between revisions of "1999 USAMO Problems/Problem 1"

Latest revision as of 04:23, 13 May 2023

Problem

Some checkers placed on an $n\times n$ 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 $(n^{2}-2)/3$ checkers have been placed on the board.

Solution 1

For the proof let's 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 $x$ 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, $4\times x + x = 5\times x \ge n^2$ (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 $5\times x - \text{[sum of degrees in G]} \ge n^2.$

4. Thus, $5x - (2x - 2 + 2R) \ge n^2$ (see lemma below).

5. Thus, $3x + 2 - 2R \ge n^2.$

6. Thus, $x \ge \frac{n^2 - 2 + 2R}3,$ where $R\ge0$ and is equal to 0 if $G$ is a tree.

$\textit{Clarification/Lemma:}$ The sum of degrees of a connected graph $G = (V,E)$ is $2V -2 + 2R = 2E,$ where $R$ is the circuit rank of $G$ .

$\textit{Proof.}$ $2 \times V -2$ is the sum of ranks of the spanning tree created by decircuiting the graph $G$ . Since the circuit rank of $G$ is $R$ , $2R$ is the sum of ranks removed from $G$ . Thus, $2V -2 + 2R = 2 E.$ $\blacksquare$

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 $k$ checkers on the board, sitting on squares $s_1, \ldots, s_k$ . We can assume WLOG that $s_1, \ldots, s_k$ is ordered in such a way that if $1 \leq i \leq k$ , then $s_i$ shares a side with at least one of $s_1, \ldots, s_{i - 1}$ . (If such an ordering were impossible, then there would be an $s_i$ which isn’t connected to $s_1$ 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 $s_1, \ldots, s_k$ in that order, counting the number of good squares after each step. When we put a checker on $s_1$ , we increase the number of good squares by at most 5: the square $s_1$ becomes good, and each square it shares a side with (at most 4) becomes good. When we put a checker onto $s_i$ , where $i > 1$ , we increase the number of good squares by at most $3$ , since $s_i$ is already good, and at least $1$ of its at most $4$ neighbors already has a checker on it.

So the total number of good squares when we’ve put back every checker is at most $5 + 3(k - 1) = 3k + 2$ . In order to satisfy condition (a), we have to make each of the $n^2$ squares good. In other words, we need $3k + 2 \geq n^2$ , or $k \geq \frac{n^2 - 2}{3}.$

@@ Line 8: / Line 8: @@
 Prove that at least <math>(n^{2}-2)/3</math> checkers have been placed on the board.
-== Solution ==
+== Solution 1 ==
-{{solution}}
+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.
+Define <math>R</math> as the circuit rank of <math>G</math>(the minimum number of edges to remove from a graph to remove all its cycles).
+Define <math>x</math> as the number of checkers placed on the board.
+. From (a) for every square containing a checker there can be up to 4 distinct squares without checkers; thus, <math>4\times x + x = 5\times x \ge n^2</math> (this is the most naive upper bound).
+. 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).
+. 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 <math>5\times x - \text{[sum of degrees in G]} \ge n^2.</math>
+. Thus, <math>5x - (2x - 2 + 2R) \ge n^2</math> (see lemma below).
+. Thus,  <math>3x + 2 - 2R \ge n^2.</math>
+. Thus,  <math>x \ge \frac{n^2 - 2 + 2R}3,</math> where <math>R\ge0</math> and is equal to 0 if <math>G</math> is a tree.
+<math>\textit{Clarification/Lemma:}</math> The sum of degrees of a connected graph <math>G = (V,E)</math> is <math>2V -2 + 2R = 2E,</math> where <math>R</math> is the circuit rank of <math>G</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 ==
@@ Line 15: / Line 52: @@
 [[Category:Olympiad Combinatorics Problems]]
+{{MAA Notice}}

1999 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "1999 USAMO Problems/Problem 1"

Latest revision as of 04:23, 13 May 2023

Contents

Problem

Solution 1

Solution 2

See Also