Author |
Topic: an infinite chess board problem (Read 1419 times) |
|
thedkl
Newbie
Posts: 18
|
 |
an infinite chess board problem
« on: Nov 13th, 2005, 12:56pm » |
 Quote  Modify
|
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 ( )
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
|
Re: an infinite chess board problem
« Reply #1 on: Nov 13th, 2005, 1:57pm » |
Quote Modify
|
Ok, suppose not all numbers are equal.
Then 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. 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.
|
| « Last Edit: Nov 13th, 2005, 2:05pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: an infinite chess board problem
« Reply #2 on: Nov 13th, 2005, 4:17pm » |
Quote Modify
|
on Nov 13th, 2005, 1:57pm, 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 Xn be a simple random walk in the plane, starting at some point (x,y). That is, X0=(x,y), and Xn+1 is uniformly and independently chosen from one of the four neighbors of Xn.
Then the fact that f is harmonic implies that f(Xn) is a martingale: loosely speaking, the expected value of f(Xn+1), given X0,X1,...,Xn, is equal to f(Xn).
Let T be the first n for which Xn=(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(X0)) = E(f(XT))=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?
|
|
IP Logged |
|
|
|
thedkl
Newbie
Posts: 18
|
|
Re: an infinite chess board problem
« Reply #3 on: Nov 13th, 2005, 9:10pm » |
Quote Modify
|
jock, larger and larger values does not imply a contradiction to boundedness (for example 1-1/n is bounded by 1)
Eigenray, there is a very elementary solution!
|
|
IP Logged |
|
|
|
thedkl
Newbie
Posts: 18
|
|
Re: an infinite chess board problem
« Reply #4 on: Nov 14th, 2005, 11:59pm » |
Quote Modify
|
i add 3 hints. yet i strongly recommend not reading all of them at once.
1. if you have 2 infinite chess boards with the above properties then their sum/difference also has these properites.
2. check the infinite chess board made by substracting from every square the value to its east. call it the "difference board".
3. choose a square with a value near the supremum of the "difference board". its neighbours must also have values near the supremum.
after reading hint 3 the solution is trivial.
enjoy.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print