on another thread

Printable View

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

- May 5th 2009, 05: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.

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 , each such block consisting of two copies of the previous block, on the diagonal; and two copies of the previous block with 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, 10:11 AMAquafina
thanks

will i require a formal proof to generalise it or can i work with this to be enough? - May 5th 2009, 11: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, 11: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, 07: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, 12:23 PMAquafina
the proposition: