Each square of a chessboard contains a number that is equal to the average of the numbers in the squares adjacent to it. What is the maximum possible difference between the maximum number and the minimum number in the chessboard?

Sunday, August 7, 2011

Please email your solutions to puzzles@cotpi.com.

### 3 comments

### Credit

This puzzle is taken from folklore.

## Rajesh Balakrishnan solved this puzzle:

If every number is the same then the average is the same number and the first criteria is fulfilled. Let's say that there is a max possible difference of 'm' between the max and min numbers on the chessboard. I could easily multiply every number on the board by '2' and make the difference '2m'. So either m is infinity or zero.

Let us say that infinity (or a very large number) as the difference is the answer. So in one square there will be the smallest number and in some other square there will be a very huge number. But for a square to have the smallest number as the average value all neighbours have to be the smallest number or some number has to be less than the smallest number.

For simplicity let's just agree on zero :-). Or cook up a chessboard with infinity on each square (average infinity, difference infinity) and it will all make NaN-sense :-)

## Indhu Bharathi solved this puzzle:

Answer is 0. All numbers in the board should be the same.

Let me give a proof by contradiction.

Assume you have a board with more than one number and the board meets the criteria of the question. — (1)

Make a list of numbers that have different neighbors than itself. Let's call this list L.

Find the max element in L and call this element EL. So, EL cannot have a neighbor greater than itself. — (2)

Since it has atleast one neighbor not equal to itself, that neighbor should be less than EL. — (3)

From (2) and (3), EL cannot be the average of its neighbors contradicting the assumption (1).

## Dan Hoey solved this puzzle:

The average of a collection of numbers must be either equal to every number in the collection or strictly less then the greatest number in the collection. Thus every square with the maximum value must be equal to all of its neighbors. By induction, every connected component containing the maximum value must be constant. Since the neighborhood graph of the chessboard is connected, every square must be equal.