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:
Answer:
First note that if , then condition (ii) is vacuously satisfied, so the one cell must contain 0 . Henceforth, we assume that or , so that every cell has at least one adjacent cell.
We define the distance between two cells to be , where are the centers of the respective cells. In particular, two cells are adjacent if and only if the distance between them is 1 .
By condition (ii), the smallest value among the cells of any given garden must be 0 . In particular, a garden has at least one zero.
We construct an explicit bijection between the set of nonempty subsets of the cells in the array filled with 0 and the set of all possible gardens. Given a subset of the cells filled with zeroes, fill every cell in the array with the value of the distance to the nearest cell filled with a zero. This filling of the cells is well-defined and satisfies both properties (i) and (ii). Given two different subsets of cells filled with zeroes, the filling of all cells with minimum distances must necessarily be different, so the function is injective (or one-to-one).
Let an arbitrary garden be given and suppose that a cell in that garden contains an integer . By condition (ii), it has an adjacent cell with a smaller integer. Since the difference is either 0 or 1 , the difference must be 1 . Thus, a cell assigned will have an adjacent cell assigned . We draw a line segment between the two center points of these two cells. Repeating this procedure, we can find a path from to a 0 -cell. We call such a path a garden path. There may be more than one garden path from a given cell, but all such paths will have length .
Suppose that for some cell assigned there is a path of length from to a 0 -cell . Let the numbers in the cells the path goes through be . Now , so
a contradiction. Thus, the nearest 0 -cell to has distance from . By the previous paragraph, there exists a path from to a 0 -cell with distance . Therefore, the distance to the nearest 0 -cell is exactly . The mapping is surjective (or onto).
Therefore, each garden is uniquely determined by the position of zeros. Consequently, we just need to count the number of ways to put zeros in cells, subject to the condition that there is at least one zero. This is clearly .
This problem and solution were suggested by Sungyoon Kim.
The problems on this page are the property of the MAA's American Mathematics Competitions