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

1999 USAMO Problems/Problem 1

Revision as of 06:09, 25 January 2013 by Haimshimonovich (talk | contribs) (submit)

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"