wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> an infinite chess board problem
        
(Message started by: thedkl on Nov 13^th, 2005, 12:56pm)

Title: an infinite chess board problem
Post by thedkl on Nov 13^th, 2005, 12:56pm

1) we have an infinite chess board with a real number on every square.
2) each number is the average of the numbers in the squares to its north, west, south and east.
3) the numbers are bounded in their absolute value.

prove that all the numbers are equal (:o)

Title: Re: an infinite chess board problem
Post by JocK on Nov 13^th, 2005, 1:57pm

Ok, suppose not all numbers are equal.

Then [hide]there must be a square surrounded by four numbers that are not all equal. Start at this square. One of these four surrounding numbers is the largest, and also larger than the number on the central square (because the value of the central square equals the average of the values of the surrounding squares). Go to the square with this largest number.

# On this new square, one of the four surrounding squares (the square you come from) carries a value smaller than the current square. So there must also be a surrounding square with a number larger than that at the current square. Go to this square and repeat (goto #).

The result is that you hop from square to square to larger and larger values.[/hide] This is in conflict with the stated condition that all numbers are bounded.

Hence, the assumption (not all numbers are equal) can not be maintained.

Title: Re: an infinite chess board problem
Post by Eigenray on Nov 13^th, 2005, 4:17pm

on 11/13/05 at 13:57:13, JocK wrote:

The result is that you hop from square to square to larger and larger values. This is in conflict with the stated condition that all numbers are bounded.

Is it?

Here's a slick proof I saw in a probability class:
Suppose f : ZxZ -> R is bounded and harmonic, i.e., for all x,y, f(x,y) is the average of f(x',y'), over the 4 neighbors of (x,y).
Let X_n be a simple random walk in the plane, starting at some point (x,y). That is, X₀=(x,y), and X_n+1 is uniformly and independently chosen from one of the four neighbors of X_n.
Then the fact that f is harmonic implies that f(X_n) is a martingale: loosely speaking, the expected value of f(X_n+1), given X₀,X₁,...,X_n, is equal to f(X_n).
Let T be the first n for which X_n=(0,0). It is well-known that T<[infty] with probability 1. Moreover, since f is bounded, it follows from the optional stopping (sampling) theorem that
f(x,y) = E(f(X₀)) = E(f(X_T))=f(0,0).
But since (x,y) was arbitrary, it follows f is constant.

However there's quite a bit of analysis hidden in the background. Is there an elementary proof?

Title: Re: an infinite chess board problem
Post by thedkl on Nov 13^th, 2005, 9:10pm

jock, [hide]larger and larger values does not imply a contradiction to boundedness (for example 1-1/n is bounded by 1)[/hide]
Eigenray, there is a very elementary solution!

Title: Re: an infinite chess board problem
Post by thedkl on Nov 14^th, 2005, 11:59pm

i add 3 hints. yet i strongly recommend not reading all of them at once.

1. [hide]if you have 2 infinite chess boards with the above properties then their sum/difference also has these properites.[/hide]

2. [hide]check the infinite chess board made by substracting from every square the value to its east. call it the "difference board".[/hide]

3. [hide]choose a square with a value near the supremum of the "difference board". its neighbours must also have values near the supremum.[/hide]

after reading hint 3 the solution is trivial.

enjoy.