26 Oct '08 20:45

I've got 4 chess boards. I Wrote a number in the range 1-64 in each square of each board, in such a way that any combination of 2 distinct numbers between 1 and 64 can be found in the same rank, same file or same long diagonal.

For example, 20 and 50 are 2 distinct numbers between 1 and 64. So somewhere in the 4 boards these numbers can be found in the same rank, same file or same long diagonal of 1 board.

Easy part:

Prove that actually any combination of 2 distinct numbers between 1 and 64 can be found EXACTLY ONCE in the same rank, same file or same long diagonal.

Prove that on each board are written all the number 1-64.

Hard part:

Construct such boards.

Maybe it will be a little bit clearer if I rephrase it in the language of graph theory. I have 4 chess boards. Let each square of each board be a node of our graph. Two nodes will be adjacent iff they belong to the same chessboard, and they are on the same rank, file or long diagonal. So each node has 14 or 21 neighbours. Required: assign each node an integer in [1,64], in such a way that for each pair of distinct integers m,n in [1,64] there will be adjacent nodes numberd m and n.

For example, 20 and 50 are 2 distinct numbers between 1 and 64. So somewhere in the 4 boards these numbers can be found in the same rank, same file or same long diagonal of 1 board.

Easy part:

Prove that actually any combination of 2 distinct numbers between 1 and 64 can be found EXACTLY ONCE in the same rank, same file or same long diagonal.

Prove that on each board are written all the number 1-64.

Hard part:

Construct such boards.

Maybe it will be a little bit clearer if I rephrase it in the language of graph theory. I have 4 chess boards. Let each square of each board be a node of our graph. Two nodes will be adjacent iff they belong to the same chessboard, and they are on the same rank, file or long diagonal. So each node has 14 or 21 neighbours. Required: assign each node an integer in [1,64], in such a way that for each pair of distinct integers m,n in [1,64] there will be adjacent nodes numberd m and n.