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"

(Dexterito has been spamming, and banned.)
(submit)
Line 9: Line 9:
  
 
== Solution ==
 
== 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 $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 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 $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 >= 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 -$(sum of degrees in G)$>= n^2$

4. thus, $5\times x - (2 \times x - 2 + 2\times R) >= n^2$ (see lemma below).

5. thus, $3\times x + 2 - 2\times R >= n^2$

6. thus, $x >= (n^2 - 2 + 2\times R)/3$

where $R>=0$ and is equal to 0 if G is a tree.

$clarification/lemma:$

the sum of degrees of a connected graph $G = (V,E)$ is $2 \times V -2 + 2\times R = 2\times E$

where $R$ is the circuit rank of $G$.

$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$, $2\times R$ is the sum of ranks removed from $G$.

thus, $2 \times V -2 + 2\times R = 2\times E$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_USAMO_Problems/Problem_1&oldid=50591"