16. Alisha wrote an integer in each square of a $4 \times 4$ grid. Integers in squares with a common edge differed by 1 . She wrote a 3 in the top left corner, as shown. She also wrote a 9 somewhere in the grid. How many different integers did she write?
A 4
B 5
C 6
D 7
E 8
SolUtion
D

Since the integers in squares with a common edge differ by 1 , the integers in the two squares with a common edge to the square with a 3 in are either 2 or 4 . Hence they are both $\leq 4$. Similarly, if the integer in a square is $\leq 4$, then the integers in the squares with a common edge to that square are $\leq 5$, and so on. This gives a set of inequalities for the integers in all the squares, as shown in Figure 1.

Since only one square could contain an integer as big as 9 and we are told that Alisha wrote a 9 somewhere in the grid, the 9 must be in the bottom right corner. The integers in the squares with a common edge to the square with a 9 in are either 8 or 10 . Hence they are both $\geq 8$. We can continue this process in a similar way to obtain a second set of inequalities for the integers in all the squares, as shown in Figure 2.

An integer that is both $\leq n$ and $\geq n$ must be $n$. Therefore, from the inequalities given for the integers in all the squares in Figures 1 and 2, we can deduce that the integers Alisha wrote were as shown in Figure 3. From this we see that Alisha wrote only the integers 3, 4, 5, 6, 7, 8 and 9 in the grid. Hence she wrote seven different integers in total.