Maths Olympiad Prep

Library / /25 of 34

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

Each cell of an m×nm\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 00 or 11 .
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to 00 .
Determine the number of distinct gardens in terms of mm and nn .

A number or a short expression. Spacing and $ signs are ignored.

Solution

We claim that any configuration of 00 '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 00 that is decreasing, which means that the value of the cell must be its distance from the 00 \rightarrow as the path must end. From this, we realize that, for any configuration of 00 's, the value of each of the cells is simply its distance from the nearest 00 , and therefore one garden is produced for every configuration of 00 's.
However, we also note that there must be at least one 00 in the garden, as otherwise the smallest number in the garden, which is less than or equal to all of its neighbors, is >0>0 , which violates condition (ii)(ii) . There are 2mn2^{mn} possible configurations of 00 and not 00 in the garden, one of which has no 00 's, so our total amount of configurations is 2mn1\boxed{2^{mn} -1}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.