Given an infinite grid of real numbers between 0 and 100, such that every number in the grid is the average of its four direct neighbours (the numbers to the left, right, above, and below it) prove that all the numbers are necessarily equal, or give a counter-example.

Call me a cheater, but this can be reduced to a 2-D EM (electro-magnetism) problem. The average rule can be also be seen as the numerical aproximation to laplace's equation to a continious function V(x,y),

Laplacian V(x,y) = 0

You can look at this mathworld page (equation 6) to see the details.

Therefore, directly borrowing a solution from EM, I summit the following counter-example;

Draw a 4x4 square on your grid (the actual size does not really matter). Set the points on the perimeter of the square at a constant "voltage" V_0 = 100. Give all the other points any inital value you want (for example 0). Apply the average rule over and over again (but remember that the points on the square's perimeter are always kept at V_0 = 100). You will aproach a CONVERGING solution where all the points inside the square have a value of 100 and the points outside the square have values lower than 100, tending to 0 towards infinity.

The solution is identical to numerically solving laplace's equation for the potential field of a rectangular hollow tube of infinite lenght in z kept at voltage V_0. The bigger the square, the better the numerical solution will be because you are chopping up space finer. You might recognize electric field 0 inside the tube and non-0 outside of it.

Posted by ajosin on 2005-06-04 02:15:41