Difference between revisions of "2013 USAJMO Problems/Problem 2"

Line 2: Line 2:
 
   
 
   
 
(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 0 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> .

Revision as of 19:31, 11 May 2013

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$ .