Chessboard Proof

**gfbrd** · October 16th 2012, 10:12 AM

Hey there I also need some help on this proof as well.

Imagine an infinite chessboard that contains a positive integer in each square. If the value in each square is equal to the average of its four neighbors to the north, east, south and west prove the values in all the squares are equal.

I understand this problem conceptually, but I can seem to put this in words. I hope someone can guide me through the problem step by step, so I can understand how to do this problem, thanks.

**johnsomeone** · October 16th 2012, 10:51 AM

$\text{Model a solution as }\phi : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+ \ni \phi(x,y) = \frac{\phi(x+1, y) + \phi(x, y+1) + \phi(x-1, y) + \phi(x, y-1)}{4}.$

$\text{Consider the set } \{\phi(x, y) | (x,y) \in \mathbb{Z} \times \mathbb{Z} \} \subset \mathbb{Z}^+.$

$\text{By well ordering, that set has a minimal element, call it }r.$

$\text{Have that there exists } (x_0, y_0) \in \mathbb{Z} \times \mathbb{Z} \text{ such that } \phi(x_0, y_0) = r.$

$\text{Have that } \phi(x_0, y_0) \text{ is the average of its four neighbors, and each of them has value at least } r.$

$\text{Therefore each of them equals } r, \text{ because if even one of them were greater than } r,$

$\text{that would imply that } \phi(x_0, y_0) > r.$

$\text{Thus }\phi(x_0+1, y_0) = \phi(x_0, y_0+1) = \phi(x_0-1, y_0) = \phi(x_0, y_0-1)} = r.$

$\text{Repeat that reasoning with the four neighbors of } (x_0, y_0) \text{ and then with their neighbors, etc., }$

$\text{until it's spread everywhere, to prove that } \phi(x, y) = r \ \forall \ (x, y) \in \mathbb{Z} \times \mathbb{Z}.$

$\text{Knowing the reason it's true, you can hopefully write up a technical proof that it's true,}$

$\text{Hint: show it's true vertically though } (x_0, y_0) \text{ for } (x_0, y_1), \text{ and then horizontally for } (x_1, y_1).$

**gfbrd** · October 16th 2012, 02:43 PM

Hey thanks a lot for getting me started on this problem, just one question I'm not exactly sure what those symbols mean like phi and ZxZ. I am hoping you can let me know what they mean just so I can understand what each part means.

**johnsomeone** · October 16th 2012, 03:25 PM

$\mathbb{Z} \text{ is the symbol used to indicate the set of integers, } \mathbb{Z} = \{... -3, -2, -1, 0, 1, 2, 3, 4, ... \}$

$\mathbb{Z}^+ \text{ is the symbol used to indicate the set of positive integers, so } \mathbb{Z}^+ = \{ 1, 2, 3, 4, ... \}$

$\phi \text{ is just the name of a function. You could replace } \phi \text{ by } f \text{ everywhere if you like.}$

$\mathbb{Z} \times \mathbb{Z} \text{ is the "Cartesian product" of those two sets.}$

$\text{That's the set of ordered pairs of elements of those two sets, the 1st from the 1st, and the 2nd from the 2nd.}$

$\text{So ordered pairs like }(-5, 71), (8, 13), \text{ etc. are what are in the set } \mathbb{Z} \times \mathbb{Z},$

$\text{since for each of them, the 1st coordinate (like -5) is in }\mathbb{Z} \text{ and the 2nd coordinate (like 71) is in } \mathbb{Z}.$

$\text{This is function notation: }\phi : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+,$

$\text{which means that }\phi \text{ is a function with domain } \mathbb{Z} \times \mathbb{Z} \text{ and range } \mathbb{Z}^+.$

$\text{So }\phi(x, y) \text{ is the value in the square labelled } (x, y), \text{ where } x \text{ and } y \text{ are integers.}$

$\text{Since each labelled square }(x, y) \text{ has a value that's a positive integer, }\phi(x, y) \text{ is a positive integer.}$

$\text{Thus the range of }\phi \text{ is all positive integers. So we write that }\phi(x, y) \in \mathbb{Z}^+.$

**gfbrd** · October 16th 2012, 04:08 PM

Oh I see now, thanks I understand it better now

Thread: Chessboard Proof

LinkBack

Thread Tools

Display

Chessboard Proof

Re: Chessboard Proof

Re: Chessboard Proof

Re: Chessboard Proof

Re: Chessboard Proof

Similar Math Help Forum Discussions

ChessBoard

Chessboard

Chessboard

the chessboard

Tiling a chessboard

Search Tags