Supposedly the answer is $2^{mn} - 1$, I didn't solve it though.

agreed yayayayayyayayayayaya

So here's my bad "solution"! Tile an $m \times n$ grid with $0$s and $1$s such that not all the squares are 1. Then, follow this procedure: If a square is tiled with a positive integer such that all the adjacent squares are tiled with the same number, add one to the number. A 'step' is simultaneously checking all $mn$ squares and operating as necessary. Since the grid is not all 1s, this process must end. Obviously each tiling maps to exactly one final result. We show that the final result is always a garden. Any two adjacent squares differ by at most 1 in the original tiling. If they differ by 1, then neither of them will ever be operated on. Thus 2 adjacent squares never differ by more than 1, satisfying condition (i). If an original tile is a 1, the only way it can be <= to all the adjacent squares is if they are all equal to 1, in which case the tile is operated on. It is clearly impossible for a tile to be tiled 1, have all the adjacent tiles not 1, and the adjacent tiles are all operated on, because this would imply that the tile is also operated on. If the original tile is a 0 then this is fine. So condition (ii) is satisfied. So now we need to show that each garden can be represented in this form (oops). Fortunately this is easy since you just do the process in reverse and you're done. Thus the answer is $2^{mn}-1$ (since we excluded all 1s).

msinghal wrote: you surround the 0's with 1's, surround the 1's with 2's, etc Darn I thought about this but thought it'd be too complicated.

What was the "bijection" solution?

Bijection to m*n grids of 1's and 0's excluding the grid of all 1's which is what I did

There's a bijection between gardens and combinations of 0's.

hmm possible 1 or 2 points for proving the algorithm for a 1 x n garden?

lucylai wrote: There's a bijection between gardens and combinations of 0's. Exactly what I did, by going backwards from a board fully tiled with 0s, changing one 0 at a time. Also proved that there cannot be a configuration with zero 0s via contradiction.

Here's a rigorous solution:

I didn't do this, but the way the question is phrased: if you wrote 2^mn - 1 without proof, would you get credit? It only says determine, not necessarily show the steps leading to the formula..

You would probably receive a very small amount of point(s) if any. Showing your steps is important.

^probably not, since most people taking the JMO could probably deduce the formula AIME-style

^ yeah, I failed and thought that (1, 3) was 6 so immediately dismissed exponents for finding the formula. Probably should have checked my work... missed the 000 case.

I originally had 1x2 -> 2, 1x3 -> 9, 2x2 -> 12. Needless to say, it took me a while before I got very far.

The way I did it was with PIE, based on the number of 0's there were. I noticed that for small cases, if I put down k 0's, there would be $2^{mn - k}$ possibilities for the other cells (they can also be 0). Therefore \[total = \binom{mn}{1} (2)^{mn - 1} - \binom{mn}{2} (2) ^ {mn - 2} + \cdots + \binom{mn}{mn}(-1)^{mn - 1}\] This is a portion of a binomial expansion. Thus the total can be rewritten: \[total = 2^{mn} - (2-1)^{mn} = 2^{mn} - 1\] The problem is I don't know how there would be $2^{mn - k}$ possibilities if we put $k$ 0's down.

Note that a unique configuration is determined if we know which squares are zero. This is because we have that then for every square, if the closest square is $n$ units away from it then it must be $n$. Otherwise, there will be numbers that are less than all adjacent numbers but nonzero because of the closest square that is zero from it being less than that many units away. As a result, our answer is that there are $2$ ways to choose each square: zero or nonzero. Since not all squares are nonzero, our answer is $\boxed{2^{mn}-1}$.

The answer is $\boxed{2^{mn}-1}$. We first prove a claim: Claim: Any configuration of a positive number of 0s in the grid will determine a unique filling. Pf: We prove the existence and uniqueness of the configuration separately. To show its existence, note that we can use the following algorithm to build our filling from a configuration of 0s: 1. Surround all the adjacent squares to 0s with 1s(some of these square may be adjacent to more than 1 square containing a 0) 2. Any square that is adjacent to at least one 1 should be filled with a 2(which is not already a 0) 3. Any square that is adjacent to at least one 2 should be filled in with a 3 4. Continue this process, filling the squares that are adjacent to at least one $n$ with an $n+1,$ until the entire grid is filled. Notice that every square with an $n$ which is not $0$ must be adjacent to $n-1,$ so at the end, all of the squares will be filled in. Furthermore, each $0$ is adjacent to all $1$s, which works, and each number $c$ in the grid is adjacent to at least one square which has a $c-1,$ so each number satisfies condition (ii). To prove it satisfies condition (i), notice that the smallest number that a square containing number $n$ can be adjacent to is $n-1$(by construction, because if there was any other smaller square, some other square with a smaller number had already been adjacent to it), and the number $n+1$ can also be adjacent to it, but nothing above that(as if there was a square with number $n$ available, $n+1$ would have taken it). Therefore, this construction satisfies both conditions. Now we establish the uniqueness of this construction. On the first move, surrounding the 0s by 1s is the only thing you can do(or else you would be adding more 0s). Notice that any number adjacent to a $1$(that is not already a 0) must be a 2, because if were not, it would either be a 1 or a 0, the second of which is clearly impossible. However, if it were a 1, you would have to add another 0(because the rest of the 0s have already been surrounded by 1s), a contradiction. This also show that there can be no more 1s, as any 1s result in more 0s. Similarly, we can induct like this, with each number adjacent to $n$ having to be $n+1,$ because if it were $n$ or $n-1,$ then you would have to have another $n-1,$ but by the induction hypothesis, $n-1$ cannot be used anymore. This establishes uniqueness. We have a second claim: Claim: There must be at least one 0. Pf: Suppose there was no 0. This means that each number has at least one adjacent number which it is strictly greater than. Suppose the largest number is $a_1$. Then we can form the inequality chain $a_1>a_2>a_3\cdots, >a_n$ where we choose one of the numbers in the adjacent square that a square is greater than. However, notice that this inequality chain has to end at some square, and this square has a number less than all the squares in the grid, so it must be a 0, a contradiction. Note: There is no way for this path to "fold back" on itself because any number later in the chain is strictly less than any number prior. With these claims, the answer is obviously true, so we are done.

I don't usually write up (or solve) USA(J)MO problems so I don't have a very good sense on what is considered rigorous and would receive a $7$. As such, any feedback on the following proof would be really appreciated . Thanks in advance!

There are $2^{mn}-1$ gardens. I claim that any garden is determined by the placement of the zeroes. As a construction, all non-zero values must be the taxicab distance from the nearest 0. We now prove that this is unique. For any square A, we let $d(A)$ be the distance to the nearest 0, and let $f(A)$ be the value assigned to A. We have that $f(A)\leq d(A)$ because there exists a path with $d(A)$ "steps" from 0 to A, each "step" can only increase the value by at most 1, so $f(A)\leq d(A)$ We now show that $f(A)\geq d(A)$. Assume FTSOC that there exist such A such that $f(A)< d(A)$. Since $mn$ is finite, take the square A with the largest value of $d(A)-f(A)=x$, with ties broken by choosing a smaller $d(A)$. Then, $f(A) = d(A)-x$. Then, we clearly have that this square $f(A)$ cannot be greater than any of its neighbors, so due to condition (ii), $f(A)=0 \rightarrow d(A)=0$ which is absurd. Finally, we note there exists a square $\leq$ all other squares by starting from some square and going to a neighbor that is smaller, thus there is always at least one '0'. Therefore, we can choose each individual square to be '0' or not with at least 1 '0', which gives us a total of $2^{mn}-1$ different possible gardens.

Define the distance between two cells to be the length of the shortest possible path of adjacent squares connecting the two Claim: If a cell is numbered $a$, then the distance from the nearest zero is equal to $a$. This is true because given a nonzero cell numbered $k$, we will always find an adjacent cell equal to $k-1$ and we will never find an adjacent cell numbered less than $k-1$. So the number of the square we are at on the path decreases by exactly $1$ each time we go to a new square (if it decreases by less than $1$, the path will not be the shortest). Thus, the distance will be equal to $a$.

subsets from a set with length $mn$, which is $\boxed{2^{mn}-1}$.

Notice that a 0 must exist because if the smallest number on the board is $k$ then all other numbers are $\ge k$ which means $k=0$. Claim 1. The value of a cell is equal to the manhattan distance from the nearest 0. Proof. We use induction. Base case is obvious. Now assume that the cell with value $n-1$ is a distance of $n-1$ from the nearest 0. Because of the second condition, this cell must have an adjacent cell with value of $n$. Thus we are done because the distance increases by 1. $\blacksquare$ So the board is uniquely determined by the placement of the 0's which means that the answer is $2^{mn}-1$ because the board must have at least 1 0.

This feels like a somewhat superficial problem but it's actually a bit difficult. The answer is $2^{mn}-1$. In particular, we will show it suffices to choose the locations of the (nonzero amount of) zeroes on the grid. Obviously there is a minimal number in the grid, so there is at least one zero. To show this, we prove the stronger claim that the number in each square corresponds to its taxicab distance to the nearest zero. This can simply be done by inducting on the numbers in the grid. Assuming that all numbers at most $k$ are confined to the corresponding squares distance at most $k$ from a zero, notice that all squares of distance $k+1$ are adjacent to a square with distance $k$. As they cannot contain $k-1$ by the inductive hypothesis, they must contain $k+1$. On the other hand, $k+1$ cannot appear anywhere else because by the second condition, it must border at least one number strictly less than it, but the locations of all numbers at most $k$ are already determined.

Clearly, there must exist zeros, or else the minimum cell value would violate condition ii. We claim that every selection of zeros determines the entire grid, making our answer $2^{mn}-1$. Start with the grid totally unfilled, except for the zeros. For each $i$ from $0$ to $69420mn$, for each cell with value $i$, we fill each of its unfilled adjacent cells with value $i+1$. This must happen because otherwise, the cell would've already been filled by some previous step in the process, and our process is forced when $i=0$. Therefore, our answer is $2^{mn}-1$.

The answer is $2^{mn}-1$ because there is a one-to-one correspondence between grids whose values are all $1$ or $0$ but not all $1$'s, and gardens of the same size. Given a $1$ & $0$ coloring of a grid, repeatedly pick all nonzero numbers less than or equal to all their neighbors and increase them by $1$. This must terminate eventually since the maximum value of any cell is $mn$; furthermore, no numbers will differ by $2$ since then we wouldn't have incremented the larger one a second time. Therefore when the process terminates we have a garden. In the opposite direction, starting with a garden, we can replace all positive numbers with a $1$ to get the same $1$ & $0$ coloring.

We claim that the answer is $2^{mn}-1$. We claim that there is a bijection between the set of all gardens and the set of all grids with only $0$'s and $1$'s with $>0$ number of $0$'s. We call this grid binary. It's easy to see that a garden has a corresponding binary grid by simply setting all nonzero numbers to $1$. Then the binary grid can simply erase all the $1$'s. Then, for every $k \geq 0$, we set all nonempty cells that are adjacent to a cell filled with $k$ to $k+1$. This fulfills the minimality requirement and all other requirements as well. Thus, we just have $2^{mn}-1$ gardens because there are $2^{mn}-1$ binary grids.

Our answer is $\boxed{2^{mn}-1}$, which is derived from the main claim that the board is fixed after choosing the location of the 0s. Also note that there must exist at least one zero to not violate the second condition. We show that the only construction for the nonzero cells is the taxicab distance from the nearest 0. Notice that as soon as we break this pattern, either by staying at the previous value or going down, there exists a strictly decreasing path to a 0. This path is then either the taxicab path to another 0, as desired, or creates a hook, which is a contradiction as we can't fill the cells inside. $\blacksquare$

The answer is $2^{mn} - 1$. We claim that the he numbers on the board are determined by the placements of the zeroes. Fix the zeroes on the board. Then the numbers adjacent to the zeroes must be ones. Then the numbers adjacent to the ones, must be twos(due to $(ii)$ and so on. This effectively forces all other numbers on the board. Hence, we can choose any configuration of zeroes that works(meaning it excludes the case where there are no zeroes). So our answer is $2^{mn} - 1$.

For a cell $C$, define its coordinate as an ordered pair $(x, y)$ where $x$ denotes the number of cells to the left of $C$ on the same row, and $y$ denotes the number of cells below $C$ on the same column. Additionally, call the taxicab distance between two cells with coordinates $(x_1, y_1), (x_2, y_2)$ as $|x_1 - x_2| + |y_1 - y_2|$. Claim 1. All cells of a garden contain the minimal taxicab distance to a $0$. Proof. Consider a cell $C$ containing the nonzero value $x$. By property (ii), there exists an adjacent cell to $C$ containing $x - 1$, and a subsequent cell adjacent to that with $x - 2$, and we can follow a path of adjacent cells until we eventually reach $0$. Note that for bounding reasons, the path is the one of minimal taxicab distance. We have proven the claim. Now to show that there is a 1-to-1 correspondence, we will prove the converse. Claim 2. All grids where a cell contains the minimal taxicab distance to a $0$ is a garden. Proof. Any cell containing a $0$ is surrounded with adjacent $1$s, hence property (i) is always satisfied. Now consider any cell $C$ containing a nonzero value $x$, and the cell of the minimal taxicab distance $D$ with a $0$ to $C$. Observe that there always exists an adjacent cell to $C$ that has a smaller taxicab distance to $D$ than $C$, hence, property (ii) is always satisfied. Collectively, we see that a grid is a garden if and only if every cell contains the minimal taxicab distance to a cell with a $0$. Now any such configuration is uniquely determined by a placement of at least one $0$ on an empty grid, which there are $2^{mn} - 1$ ways to do. Our proof is complete.

I claim the answer is $\boxed{2^{mn}-1}$, and in particular choosing a nonempty subset of the cells to be $0$ uniquely determines all of the cells. Note that there must be a minimum element, forcing the subset to be nonempty. We describe an algorithm starting from all of the zeros in the grid to uniquely determine the rest of the garden, this proving the bijection. For the first iteration, make every cell around a zero that is not already a zero a one. For the second iteration, make every cell around these ones that are not a zero or a one already a two. Continue this. Call a cell "old" if it was generated from a previous iteration. Call a cell "new" if it is being generated in the iteration we are discussing. Now we prove this is unique. All of the zeros must be surorunded by ones (or the old zeros) clearly (after all it must be zero or one but we already picked the subset of ALL of the zeros in the grid). Now all of the ones must be surrounded by twos, or the ones or zeros from previous iterations of the algorithm. If, FTSOC, a one was surrounded by a new one, for it to satisfy the second condition in the problem it must be adjacent to a zero. This is a contradiction because all of the zeros are already surrounded by old. Similarly, all of the twos must be surrounded by threes (or previous twos or ones or zeros). If it was surrounded by another one, follow the previous logic to arrive at a contradiction. If it was surrounded by a new two, then to satisfy the second condition it must be surrounded by a one. But this one must be a new one because all of the old ones were already surrounded by the old twos. Hence we must have a new one and use the previous logic to arrive at a contradiction. We can continue this argument for the rest of the iterations, proving uniqueness and we are done.

We claim that the number of $m\times n$ gardens is $2^{mn}-1$. The key claim is that a garden is uniquely determined by its cells labeled with $0$. Let $S_0$ denote the set of all cells labeled with $0$ in the garden, and recursively define $S_k$ as the set of all cells not in any $S_i$ for valid $i\le k-1$ and adjacent to a cell in $S_{k-1}$ for all positive integers $k$. We show that a cell in $S_k$ is labeled with $k$ , which would prove our claim. We proceed by strong induction. It is trivial to see that every cell is $S_1$ must be labeled with a $1$, so we move on to the inductive step. Suppose that every cell in $S_i$ is labeled with $i$ for all valid $1\le i \le k$; we show that every cell in $S_{k+1}$ is labeled with $k+1$. If $S_{k+1}$ is empty, we are done, so assume $S_{k+1}$ is not empty. From the definition of a garden, every cell in $S_{k+1}$ must be labeled with either $k-1$, $k$, or $k+1$. Let $R_k$ denote the set of cells not in $S_0, S_1, \dots, S_k$. Suppose, for the sake of contradiction, that some cell in $S_{k+1}$ is labeled with $k-1$ or $k$. Notice that if a cell of a garden is labeled with a nonzero number, then it must be adjacent to some cell in $R_{k+1}$ labeled with $k-2$ or $k-1$, respectively. Subsequently, that cell must be adjacent to some cell in $R_{k+1}$ labeled $k-3$ or $k-2$, respectively, and so on. This implies that there is a cell labeled with a $0$ in $R_{k+1}$ which is out desired contradiction. The answer extraction is now straightforward. The garden must have at least one number labeled $0$, but not necessarily more. This leaves $2^{mn}-1$ ways to choose which cells of the garden are labeled with a $0$. $\blacksquare$