1999 USAMO Problems/Problem 1: Difference between revisions
Dexterito has been spamming, and banned. |
submit |
||
| 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. | |||
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>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). | |||
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> | |||
4. thus, <math>5\times x - (2 \times x - 2 + 2\times R) >= n^2</math> (see lemma below). | |||
5. thus, <math>3\times x + 2 - 2\times R >= n^2</math> | |||
6. thus, <math>x >= (n^2 - 2 + 2\times R)/3</math> | |||
where <math>R>=0</math> and is equal to 0 if G is a tree. | |||
<math>clarification/lemma:</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 06:09, 25 January 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 | ||
