Difference between revisions of "2013 USAJMO Problems/Problem 2"
Expilncalc (talk | contribs) m (→Similar Second Solution and Inspiration) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
| 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> | ||
| + | |||
| + | ==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 <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 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}} | ||
Latest revision as of 21:33, 9 April 2018
Problem
Each cell of an 
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 
or 
.
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to .
Determine the number of distinct gardens in terms of 
and 
.
Solution
We claim that any configuration of '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 that is decreasing, which means that the value of the cell must be its distance from the 
as the path must end. From this, we realize that, for any configuration of 's, the value of each of the cells is simply its distance from the nearest , and therefore one garden is produced for every configuration of 's.
However, we also note that there must be at least one in the garden, as otherwise the smallest number in the garden, which is less than or equal to all of its neighbors, is 
, which violates condition 
. There are 
possible configurations of and not in the garden, one of which has no 's, so our total amount of configurations is 
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 . 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 : either it is or 
. If it is , 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 . 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 solutions right? NO! Take the smallest cell. It has to be via criterion (ii). So a case with zero zeros is apocryphal. Our answer is 
.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
