Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1999 USAMO Problems/Problem 1"
m (→‎Solution)
Line 9: Line 9:
  
 
== Solution ==
 
== 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.
+
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 R as the circuit rank of G(the minimum number of edges to remove from a graph to remove all its cycles).
+
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.
+
Define <math>x</math> 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, <math>4\times x + x = 5\times x >= n^2</math> (this is the most naive upper bound).
+
1. 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).
  
−
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 ).
+
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 <math>5\times x - </math>(sum of degrees in G)<math> >= n^2</math>  
+
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 <math>5\times x - \text{[sum of degrees in G]} \ge n^2.</math>  
  
−
4. thus, <math>5\times x - (2 \times x - 2 + 2\times R) >= n^2</math>   (see lemma below).
+
4. Thus, <math>5x - (2x - 2 + 2R) \ge n^2</math> (see lemma below).
  
−
5. thus,  <math>3\times x + 2 - 2\times R >= n^2</math>
+
5. Thus,  <math>3x + 2 - 2R \ge n^2.</math>
  
−
6. thus,  <math>x >= (n^2 - 2 + 2\times R)/3</math>
+
6. 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.
  
−
where <math>R>=0</math> and is equal to 0 if G 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>clarification/lemma:</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>
−
 
 
−
the sum of degrees of a connected graph <math>G = (V,E)</math> is <math>2 \times V -2 + 2\times R = 2\times E</math>
 
−
 
 
−
where <math>R</math> is the circuit rank of <math>G</math>.
 
−
 
 
−
<math>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>2\times R</math> is the sum of ranks removed from <math>G</math>.
 
−
 
 
−
thus,  <math>2 \times V -2 + 2\times R = 2\times E</math>
 
  
 
== See Also ==
 
== See Also ==

Revision as of 00:58, 27 November 2017

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

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$

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_USAMO_Problems/Problem_1&oldid=88675"