Ten distinct numbers in the table

Question

    ----------------------------------------- 
    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 
    ----------------------------------------- 
    | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
    ----------------------------------------- 
    | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
    ----------------------------------------- 
    | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
    ----------------------------------------- 
    | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 |   
    ----------------------------------------- 
    | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 
    -----------------------------------------
    | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 
    -----------------------------------------
    | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |  
    -----------------------------------------
    | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 |  
    -----------------------------------------
    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 
    -----------------------------------------
    

Is it possible to pick ten entries from this table, so that

• each row contains exactly one picked entry;
• each column contains exactly one picked entry;
• each of the numbers $0,1,2,3,4,5,6,7,8,9$ is picked exactly once?

Answer 1

It's not possible.

The parity (odd/even) of the entries follows a checkerboard pattern. Labeling the rows and columns 0 to 9 in order, the sum of the entry, its column, and its row is always even. So, summing these over all included entries must give an even number.

But, this sum must include each row 0 to 9, whose sum is odd, and likewise for the columns and entries. So, the overall sum must be odd, a contradiction.

Answer 2

As @xnor said, we can show it is not possible by using a parity argument. Let's look at a few examples of smaller tables to illustrate the argument. Let's start with the obviously impossible 2x2:

0	1
1	0

To get a 0 and a 1, with something in each of columns 0 and 1, and something in each of rows 0 and 1, we need the total sum of rows, columns, and entries to be 3. However, look at the four entries:

0 at 0,0 (sum 0)
1 at 1,0 (sum 2)
1 at 0,1 (sum 2)
0 at 1,1 (sum 2)

There's no way to get a sum of 3 because they are all even. Let's move on to a 3x3:

0	1	2
2	0	1
1	2	0

In this case, there are solutions:

* 0 *	1	2
2	0	* 1 *
1	* 2 *	0

However, look at the odds vs evens:

* 0 *	1	* 2 *
* 2 *	* 0 *	1
1	* 2 *	* 0 *

Unlike in the 10x10 table, they do not follow a checkerboard pattern. If we calculate the sums:

0 at 0,0 = 0
1 at 2,1 = 4
2 at 1,2 = 5

The overall sum is 9 - exactly what we'd expect to get from having 0, 1, and 2, with a representative from each of columns 0, 1, and 2, and a representative from each of rows 0, 1, and 2.

Now let's look at a 4x4, with the even numbers marked:

* 0 *	1	* 2 *	3
3	* 0 *	1	* 2 *
* 2 *	3	* 0 *	1
1	* 2 *	3	* 0 *

So now we know that if an entry's row+column is even, the entry is even. If the entry's row+column is odd, the entry is odd. In both cases, the parity is even. We need 0+1+2+3 from columns 0+1+2+3 and rows 0+1+2+3 = 18, which is even. Since the needed parity is even, parity does not rule out that there might be a solution.

It actually still doesn't work. The easiest way to see this is by choosing any 0, which rules out two of each of the other numbers. Then look at the two options for 2 - one rules out both the remaining 1s, and the other rules out both the remaining 3s:

0
		1	2
	3		1
	2	3

and

		2	3
	0
2			1
1		3

With a 5x5:

0	1	2	3	4
4	0	1	2	3
3	4	0	1	2
2	3	4	0	1
1	2	3	4	0

Our parity check says we need (0+1+2+3+4)*3 = 30, and we don't have a checkerboard pattern of odds and evens, so it's worth looking for a solution. It turns out there's quite an easy one to find:

* 0 *	1	2	3	4
4	0	1	2	* 3 *
3	4	0	* 1 *	2
2	3	* 4 *	0	1
1	* 2 *	3	4	0

With a 6x6:

0	1	2	3	4	5
5	0	1	2	3	4
4	5	0	1	2	3
3	4	5	0	1	2
2	3	4	5	0	1
1	2	3	4	5	0

Here the parity check fails. If we start to list out each entry:

0 at 0,0 = 0
1 at 1,0 = 2
2 at 2,0 = 4
3 at 3,0 = 6
4 at 4,0 = 8
5 at 5,0 = 10
5 at 0,1 = 6
0 at 1,1 = 2
1 at 2,1 = 4
2 at 3,1 = 6
3 at 4,1 = 8
...

it's easy to see that in each case, the sum of entry+row#+column# is even. However, to get 0+1+2+3+4+5 while representing each of columns 0+1+2+3+4+5 and rows 0+1+2+3+4+5, we need the total sum of entry+row+column to be 45, an odd number. Thus there cannot be a way to solve a 6x6.

I'm not going to go any farther, because they're getting big enough that I don't think it's easy enough to see the connection for it to be helpful. However, I did notice that odd-sized tables have a trivial way to generate a solution - choose the zero at 0,0, and then go diagonally up and to the right (wrapping around):

* 0 *	1	2	3	4	5
6	0	1	2	3	4
5	6	0	1	2	* 3 *
4	5	6	0	* 1 *	2
3	4	5	* 6 *	0	1
2	3	* 4 *	5	6	0
1	* 2 *	3	4	5	6

Answer 3

It might be possible.

The square you have provided is a latin square. While I do not know of one orthgonal to it, here is a link to a pair of orthogonal latin squares of order 10. So it is possible that there is a square orthogonal to the one you gave.

Lets assume a latin square orthogonal to the one you have given exists. Lets call these latin squares $A$ and $B$.

First, create the superposition of these two squares $C$. Thus, the entries of $C_{ij}=\{A_{ij},B_{ij}\}$.

Now, since these squares are orthogonal, we know that for every $n,m \in \{0-9\}$ there exists an entry in $C$ that is $\{n,m\}$.

Thus, we know that there exists the following entries in $C$:

$$\{0,0\}, \{0,1\}, \{0,2\}, \{0,3\}, \{0,4\}, \{0,5\}, \{0,6\}, \{0,7\}, \{0,8\}, \{0,9\}$$

Since the first number $0$ comes from square $A$, and $A$ is a latin square, we know that every $0$ comes from a different row and column of $A$. This also means that every entry containing a $0$ as the first number in $C$ must come from a different row and column of $C$. Thus, we have a set of entries in $B$, one from each row and one from each column, and all the numbers in $\{0-9\}$ are picked exactly once. So long as $B$ is the original latin square, we are done!