Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By johnsomeone

Math Help - Chessboard Proof

  1. #1
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Chessboard Proof

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Chessboard Proof

    \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).
    Last edited by johnsomeone; October 16th 2012 at 03:15 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Chessboard Proof

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Chessboard Proof

    \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}^+.
    Last edited by johnsomeone; October 16th 2012 at 04:27 PM.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Chessboard Proof

    Oh I see now, thanks I understand it better now
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ChessBoard
    Posted in the Statistics Forum
    Replies: 7
    Last Post: September 1st 2010, 08:55 AM
  2. Chessboard
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 3rd 2009, 11:16 AM
  3. Chessboard
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 18th 2009, 01:38 PM
  4. the chessboard
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 2nd 2009, 09:01 AM
  5. Tiling a chessboard
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 2nd 2009, 04:44 PM

Search Tags


/mathhelpforum @mathhelpforum