on another thread

Printable View

- May 4th 2009, 03:30 AMAquafinainfinite board
on another thread

- May 5th 2009, 04:02 AMOpalg
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.

$\displaystyle \begin{array}{cccc|cccc|cccccccc}(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.)

6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\

5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\

4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\ \cline{1-8}

3&\multicolumn{1}{c|}{2}&1&0&7&6&5&4&11&10&9&8&15& 14&13&12\\

2&\multicolumn{1}{c|}{3}&0&1&6&7&4&5&10&11&8&9&14& 15&12&13\\ \cline{1-4}

1&\multicolumn{1}{c|}{0}&3&2&5&4&7&6&9&8&11&10&13& 12&15&14\\

0&\multicolumn{1}{c|}{1}&2&3&4&5&6&7&8&9&10&11&12& 13&14&15

\end{array}$

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 $\displaystyle 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 $\displaystyle 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

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. - May 5th 2009, 09:11 AMAquafina
thanks

will i require a formal proof to generalise it or can i work with this to be enough? - May 5th 2009, 10:23 AMOpalg
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.

- May 5th 2009, 10:39 AMAquafina
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? - May 10th 2009, 06:36 PMAquafinasomething 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? - May 19th 2009, 11:23 AMAquafina
the proposition: