4
$\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$
8
$\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
    $\begingroup$ Very nice reasoning! $\endgroup$ – Fimpellizieri Oct 7 '15 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.