6
$\begingroup$

While I was working on Ten distinct numbers in the table, I found that odd-sized tables will all work. Additionally, the technique @xnor used to prove a 10x10 doesn't work does not automatically rule out 4x4 and 8x8 tables from working. A 4x4 table doesn't work, but what about an 8x8 table?

0 1 2 3 4 5 6 7
7 0 1 2 3 4 5 6
6 7 0 1 2 3 4 5
5 6 7 0 1 2 3 4
4 5 6 7 0 1 2 3
3 4 5 6 7 0 1 2
2 3 4 5 6 7 0 1
1 2 3 4 5 6 7 0

Same rules as before - can you pick the numbers 0 through 7 such that you have one of each number, with every column and row being represented exactly once each?

If this doesn't work, are there any even-sized tables that do? If it does, is there a general rule for which ones work and which don't?

Parity check: 0-7 add up to 28, so numbers+rows+columns adds up to 84. Even number passes the parity check.

$\endgroup$

1 Answer 1

10
$\begingroup$

This is impossible for an $n\times n$ table whenever $n$ is even.

If we number the rows $0,1,\ldots,n-1$ and the columns similarly, the entry in row $i$, column $j$ is congruent to $j-i$ modulo $n$. It follows that if we pick $n$ entries, one from each row and column, the sum of these entries must be divisible by $n$ (modulo $n$, each number $0,1,\ldots,n-1$ gets added once as a column number and subtracted once as a row number). So if it is possible to pick our $n$ numbers to be $0,1,\ldots,n-1$, is must be the case that $0+1+\ldots+(n-1)$ is divisible by $n$. We can compute $$ 0+1+\ldots+(n-1)=n\frac{n-1}{2}. $$ This sum is divisible by $n$ if and only if $(n-1)/2$ is an integer, i.e. if and only if $n$ is odd.

$\endgroup$
1
  • 1
    $\begingroup$ Very nice reasoning! $\endgroup$ Oct 7, 2015 at 18:05

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .