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 counterexample.
Call me a cheater, but this can be reduced to a 2D EM
(electromagnetism) 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 counterexample;
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 non0 outside of
it.

Posted by ajosin
on 20050604 02:15:41 