infinite board

[Aquafina]

on another thread

[Opalg]

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.

(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 , 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):

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.

[Aquafina]

thanks

will i require a formal proof to generalise it or can i work with this to be enough?

[Opalg]

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.

[Aquafina]

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?

[Aquafina]

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?

[Aquafina]

the proposition: