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 "2013 USAJMO Problems/Problem 2"
Line 1: Line 1:
 +
==Problem==
 +
 
Each cell of an <math> m\times n </math> board is filled with some nonnegative integer. Two numbers in the filling are said to be ''adjacent'' if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a ''garden'' if it satisfies the following two conditions:
 
Each cell of an <math> m\times n </math> board is filled with some nonnegative integer. Two numbers in the filling are said to be ''adjacent'' if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a ''garden'' if it satisfies the following two conditions:
 
   
 
   
−
(i) The difference between any two adjacent numbers is either 0 or <math> 1 </math>.  
+
(i) The difference between any two adjacent numbers is either <math>0</math> or <math> 1 </math>.  
  
 
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to  <math>0</math> .
 
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to  <math>0</math> .
 
   
 
   
 
Determine the number of distinct gardens in terms of <math>m</math> and <math>n</math> .
 
Determine the number of distinct gardens in terms of <math>m</math> and <math>n</math> .
 +
 +
==Solution==
 +
 +
We claim that any configuration of <math>0</math>'s produces a distinct garden.  To verify this claim, we show that, for any cell that is nonzero, the value of that cell is its distance away from the nearest zero, where distance means the shortest chain of adjacent cells connecting two cells.  Now, since we know that any cell with a nonzero value must have a cell adjacent to it that is less than its value, there is a path that goes from this cell to the <math>0</math> that is decreasing, which means that the value of the cell must be its distance from the <math>0 \rightarrow</math> as the path must end.  From this, we realize that, for any configuration of <math>0</math>'s, the value of each of the cells is simply its distance from the nearest <math>0</math>, and therefore one garden is produced for every configuration of <math>0</math>'s. 
 +
 +
 +
However, we also note that there must be at least one <math>0</math> in the garden, as otherwise the smallest number in the garden, which is less than or equal to all of its neighbors, is <math>>0</math>, which violates condition <math>(ii)</math>.  There are <math>2^{mn}</math> possible configurations of <math>0</math> and not <math>0</math> in the garden, one of which has no <math>0</math>'s, so our total amount of configurations is <math>\boxed{2^{mn} -1}</math>

Revision as of 20:29, 11 May 2013

Problem

Each cell of an $m\times n$ board is filled with some nonnegative integer. Two numbers in the filling are said to be adjacent if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a garden if it satisfies the following two conditions:

(i) The difference between any two adjacent numbers is either $0$ or $1$.

(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to $0$ .

Determine the number of distinct gardens in terms of $m$ and $n$ .

Solution

We claim that any configuration of $0$'s produces a distinct garden. To verify this claim, we show that, for any cell that is nonzero, the value of that cell is its distance away from the nearest zero, where distance means the shortest chain of adjacent cells connecting two cells. Now, since we know that any cell with a nonzero value must have a cell adjacent to it that is less than its value, there is a path that goes from this cell to the $0$ that is decreasing, which means that the value of the cell must be its distance from the $0 \rightarrow$ as the path must end. From this, we realize that, for any configuration of $0$'s, the value of each of the cells is simply its distance from the nearest $0$, and therefore one garden is produced for every configuration of $0$'s.


However, we also note that there must be at least one $0$ in the garden, as otherwise the smallest number in the garden, which is less than or equal to all of its neighbors, is $>0$, which violates condition $(ii)$. There are $2^{mn}$ possible configurations of $0$ and not $0$ in the garden, one of which has no $0$'s, so our total amount of configurations is $\boxed{2^{mn} -1}$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAJMO_Problems/Problem_2&oldid=52747"