Unequal Neighbors

Question

Given an $m 	imes n$ grid of integers, each cell value may be increased by at most 1. Two cells are considered neighbors if they share a side. Determine whether it is always possible to modify the grid so that no two neighboring cells contain the same value. If it is always possible, describe a method. Otherwise, provide a counterexample.

QuantSoc · Accepted Answer

Color the grid in a chessboard pattern using alternating black and white cells.

For black cells:
- If the value is already even, leave it unchanged.
- If the value is odd, increase it by 1.

For white cells:
- If the value is already odd, leave it unchanged.
- If the value is even, increase it by 1.

After performing these operations:
- Every black cell contains an even number.
- Every white cell contains an odd number.

Since every neighboring pair consists of one black cell and one white cell, every pair of neighboring cells will contain one even and one odd number. Therefore, no two neighboring cells can have the same value.

Hence, it is always possible to modify the grid so that no neighboring cells are equal.