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"

(Added solution.)
m (→‎Similar Second Solution and Inspiration)
 
Line 19: Line 19:
 
Note: "bordering" and "surrounding" mean that two cells have to touch on a side; one vertex is not good enough.
 
Note: "bordering" and "surrounding" mean that two cells have to touch on a side; one vertex is not good enough.
  
−
We note that there is no real step to begin the problem, so start by constructing the base case: put ALL the zeroes into the board. Then note that all squares bordering it (corners alone don't count) have to have <math>1</math> as their value based on constraint (i) and that all zeroes were already in. After doing that, what can a cell bordering a 1 have as its value? Either 1 or 2, based on (i). But if it were 1, then all cells surrounding it would have at least 1 as their value by (i). And by (ii) the value would have to be 0, which contradicts our initial construction. Therefore, all the cells bordering a 1 have to be 2. Looks too simple for JMO, right?
+
We note that there is no real step to begin the problem, so start by constructing the base case: put ALL the zeroes into the board. Then note that all squares bordering it (corners alone don't count) have to be <math>1</math>. After doing that, what can a cell bordering a 1 have as its value? Either 1 or 2, based on (i). But if it were 1, then all cells surrounding it would have at least 1 as their value by (i). And by (ii) the value would have to be 0, which contradicts our initial construction. Therefore, all the cells bordering a 1 have to be 2. Looks too simple for JMO, right?
−
We apply the exact same logic to a cell bordering a value <math>n</math>: either it is <math>n</math> or <math>n+1</math>. If it is <math>n</math>, however, by constraint (i) and (ii) we realize that this cell has to be 0 (because neighbors cannot be less than it), contradicting our construction again! Therefore, that cell has to be <math>n+1</math>. And so on until the grid is filled. Basically the problem reduces to finding all 0s, surrounding them with 1s, and surrounding the 1s with 2s, etc. Beautiful! I have established a bijection between the zeros placed in the grid and the arrangement, therefore there are <math>2^{mn}</math> solutions right? NO! Take the smallest cell. It has to be <math>0</math> via criterion (ii). So a case with zero zeros is apocryphal. Our answer is <math>2^{mn}-1</math>.
+
We apply the same logic to a cell bordering value <math>n</math>: either it is <math>n</math> or <math>n+1</math>. If it is <math>n</math>, however, by constraint (i) and (ii) we realize that this cell has to be 0 (because neighbors cannot be less than it), contradicting our construction again! Therefore, that cell has to be <math>n+1</math>. And so on until the grid is filled. Basically the problem reduces to finding all 0s, surrounding them with 1s, and surrounding the 1s with 2s, etc. Beautiful! I have established a bijection between the zeros placed in the grid and the arrangement, therefore there are <math>2^{mn}</math> solutions right? NO! Take the smallest cell. It has to be <math>0</math> via criterion (ii). So a case with zero zeros is apocryphal. Our answer is <math>2^{mn}-1</math>.
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 22:33, 9 April 2018

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

Similar Second Solution and Inspiration

Note: "bordering" and "surrounding" mean that two cells have to touch on a side; one vertex is not good enough.

We note that there is no real step to begin the problem, so start by constructing the base case: put ALL the zeroes into the board. Then note that all squares bordering it (corners alone don't count) have to be $1$. After doing that, what can a cell bordering a 1 have as its value? Either 1 or 2, based on (i). But if it were 1, then all cells surrounding it would have at least 1 as their value by (i). And by (ii) the value would have to be 0, which contradicts our initial construction. Therefore, all the cells bordering a 1 have to be 2. Looks too simple for JMO, right? We apply the same logic to a cell bordering value $n$: either it is $n$ or $n+1$. If it is $n$, however, by constraint (i) and (ii) we realize that this cell has to be 0 (because neighbors cannot be less than it), contradicting our construction again! Therefore, that cell has to be $n+1$. And so on until the grid is filled. Basically the problem reduces to finding all 0s, surrounding them with 1s, and surrounding the 1s with 2s, etc. Beautiful! I have established a bijection between the zeros placed in the grid and the arrangement, therefore there are $2^{mn}$ solutions right? NO! Take the smallest cell. It has to be $0$ via criterion (ii). So a case with zero zeros is apocryphal. Our answer is $2^{mn}-1$.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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