11
$\begingroup$ 
    ----------------------------------------- 
    | 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?
|improve this question
$\endgroup$
  • $\begingroup$ I don't get it. Can you give me an example what I'm looking for? $\endgroup$ – Marin Takanov Oct 7 '15 at 8:40
  • $\begingroup$ As far as I understand you chose an item from each row s.th.: there is only one chosen item per column AND the chosen item (numbers) only appears once in your list of chosen items $\endgroup$ – Aron_dc Oct 7 '15 at 8:44
21
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ If you could explain your answer a little more in depth I would surely appreciate it. I'm not sure I entirely follow what you are saying or why it means what it does. $\endgroup$ – Warlord 099 Oct 7 '15 at 14:49
  • $\begingroup$ @Warlord099 Pick any square and determine its coordinates starting with (0,0) in the top left corner. If you choose a square where the sum of the coordinates is even (like (0,0) or (2,6) or (3,5)) the number is also even, and if the coordinate sum is odd the number is odd. Even + even = even, odd + odd = even. $\endgroup$ – Kyle Hale Oct 7 '15 at 16:05
  • $\begingroup$ @Warlord099 And since even + even = even, if you pick 10 squares for the puzzle, the total sum of coordinates and numbers must be even. Per the rules you must select one square for each row and one square for each column, so the sum of these coordinates is 0+1+2...+9 (rows) + 0+1+2..+9 (columns) and the numbers selected are obviously 0+1+2..+9. That all adds up to 135, which is odd. That's the contradiction. $\endgroup$ – Kyle Hale Oct 7 '15 at 16:09
  • $\begingroup$ @KyleHale Thanks for the explanation. I see what he means now. I got confused on the last paragraph where I saw the part about summing 0 to 9. For whatever reason I wasn't making the connection to doing that three times (once each for the row/column/entry). $\endgroup$ – Warlord 099 Oct 7 '15 at 16:24
11
$\begingroup$

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 |   |   |   |      |   |   | 2 | 3 |
-----------------      -----------------
|   |   | 1 | 2 |      |   | 0 |   |   |
-----------------      -----------------
|   | 3 |   | 1 |      | 2 |   |   | 1 |
-----------------      -----------------
|   | 2 | 3 |   |      | 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 |
-----------------------------
| 6 | 0 | 1 | 2 | 3 | 4 |*5*|
-----------------------------
| 5 | 6 | 0 | 1 | 2 |*3*| 4 |
-----------------------------
| 4 | 5 | 6 | 0 |*1*| 2 | 3 |
-----------------------------
| 3 | 4 | 5 |*6*| 0 | 1 | 2 |
-----------------------------
| 2 | 3 |*4*| 5 | 6 | 0 | 1 |
-----------------------------
| 1 |*2*| 3 | 4 | 5 | 6 | 0 |
-----------------------------
|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! That's explained all I didn't understand about @xnor's answer, even though you two did say the same thing. Can you point me to a resource to understand this concept better? It sounds integral to solving a whole class of puzzles. $\endgroup$ – Anees Rao Oct 8 '15 at 3:31
  • $\begingroup$ +1 for explaining the concept in detail. I am unfamiliar with the concept of parity and didn't understand in the least what adding columns and rows could possibly have to do with whether there was a solution. It's still a little cloudy for me, but I can now see why it is relevant. $\endgroup$ – feelinferrety Mar 17 '16 at 15:17
3
$\begingroup$

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!

|improve this answer
$\endgroup$
  • $\begingroup$ This depends heavily on the assumption that this particular square has another square orthogonal to it. When there's already a convincing proof that it is not possible, this assumption is not warranted. $\endgroup$ – Rob Watts Oct 7 '15 at 16:27
  • $\begingroup$ @RobWatts Agreed. I did make that assumption, and then read the other answer. I'll leave this here, but you are correct. $\endgroup$ – Trenin Oct 7 '15 at 16:28

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.