Results 1 to 7 of 7

Math Help - infinite board

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    infinite board

    on another thread
    Attached Files Attached Files
    Last edited by Aquafina; June 10th 2009 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Aquafina View Post
    I have attached the image of the chessboard

    The squares of an infinite chessboard are numbered as follows: in the first row and first column we put 0, and then in every other square we put the smallest non-negative integer that does not appear anywhere below it in the same column or anywhere to the left of it in the same row.

    What number will appear in the 1000th row and 700th column? Can i generalize this?
    I think the number in the 1000th row and 700th column will be 348, but I don't have a complete proof of that.

    The pattern that you see from the first few rows and columns makes it clear that things happen in powers of 2.

    \begin{array}{cccc|cccc|cccccccc}<br />
6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\<br />
5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\<br />
4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\ \cline{1-8}<br />
3&\multicolumn{1}{c|}{2}&1&0&7&6&5&4&11&10&9&8&15&  14&13&12\\<br />
2&\multicolumn{1}{c|}{3}&0&1&6&7&4&5&10&11&8&9&14&  15&12&13\\ \cline{1-4}<br />
1&\multicolumn{1}{c|}{0}&3&2&5&4&7&6&9&8&11&10&13&  12&15&14\\<br />
0&\multicolumn{1}{c|}{1}&2&3&4&5&6&7&8&9&10&11&12&  13&14&15<br />
\end{array}
    (The TeX compiler used for the Forum won't allow me to display more than the bottom 7 rows. You'll have to add a couple more to make the pattern more obviously visible.)

    The bottom left 2×2 block consists of 0s on the southwest–northeast diagonal, and 1s in the off-diagonal positions. The bottom left 4×4 block consists of two copies of the bottom left 2×2 block, on the diagonal; and copies of that same block with 2 added to each element, in the off-diagonal positions. The bottom left 8×8 block consists of two copies of the bottom left 4×4 block, on the diagonal; and copies of that same block with 4 added to each element, in the off-diagonal positions. And so on, building up blocks of size 2^n\times2^n, each such block consisting of two copies of the previous block, on the diagonal; and two copies of the previous block with 2^{n-1} added to each element, in the off-diagonal positions.

    So, how do we compute the number in the (m,n)-position? The book-keeping becomes much easier if you start numbering rows and columns from 0 rather than 1. So the bottom left corner of the chessboard is row 0 and column 0. The algorithm that seems to work (though I don't have a proof for it) is to form the binary representation of m and n, and then take their bitwise sum (mod 2). That gives the binary representation of the number in the (m,n)-position.

    If it's not clear what that means, here's an example. We want to know the number in the 1000th row and 700th column. But if the numbering starts at 0 rather than 1, that means we should take m=999 and n=699. The first step is write these numbers in base 2, getting m = 11111100111 and n = 1010111011. Now "add" these numbers together, treating 1+1 as 0 (or using what computer scientists call a XOR gate):
    Code:
    1111100111
    1010111011
    0101011100
    The resulting number 101011100 is the base 2 representation of 348.

    As I said, I don't have a proof of that, but try it on some smaller numbers and you'll see that it works.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    190
    thanks

    will i require a formal proof to generalise it or can i work with this to be enough?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Aquafina View Post
    will i require a formal proof to generalise it or can i work with this to be enough?
    You told me (by PM) that this problem comes from a collection of questions that were set for the UK Senior Mathematics Challenge in the 1990s. The format of this competition has changed over the years, but I believe that at that time some of the later questions on the paper were designed to be open-ended investigations where it was not necessarily expected that competitors would obtain a complete, rigorous solution. I may be wrong, and there may be some way of proving this result that escapes me, but I would be surprised if many of the competitors would have been able to provide a formal proof of the general result.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2009
    Posts
    190
    oh okay thanks, yeah it has changed a lot but i think the book has most of its own questions too which are to prepare for general challenges. The 'generalising' part i think is probably added as an extra, but thanks

    perhaps the answer may be that no it is not able to be generalised?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2009
    Posts
    190

    something similiar...

    Hi, there is something very similiar with the latin squares:

    Nim Sum from Interactive Mathematics Miscellany and Puzzles

    Any ideas of generalising it using this?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2009
    Posts
    190
    the proposition:
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. knight on the chess board
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 15th 2011, 11:37 AM
  2. Knights of the Board
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: April 30th 2010, 08:39 AM
  3. Board Game
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 26th 2009, 11:01 PM
  4. board problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 11th 2009, 08:25 PM
  5. I have a 1x8 board...
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 17th 2008, 12:03 PM

Search Tags


/mathhelpforum @mathhelpforum