3
$\begingroup$

Here's a puzzle. We have an $N \times N$ table. Inside each cell we write two numbers, $A_{ij}$ and $B_{ij}$, where $i,j$ denote row and column index. All numbers $A$ and $B$ are integers, $A,B \in [1, N]$. The constraints are as follows

  1. For each row $i$, all numbers $A_{ij}$ are different
  2. For each row $i$, all numbers $B_{ij}$ are different
  3. For each column $j$, all numbers $A_{ij}$ are different
  4. For each column $j$, all numbers $B_{ij}$ are different
  5. There are no two cells, for which the pair $(A,B)$ would be the same

Example solution for $N=3$

$$ \begin{pmatrix} 1,1 & 2,2 & 3,3 \\ 2,3 & 3,1 & 1,2 \\ 3,2 & 1,3 & 2,1 \end{pmatrix} $$

Question: Determine for which $N$ there exists a solution. For those $N$ for which the solution exists, propose an algorithm to find 1 viable solution.

$\endgroup$
8
  • $\begingroup$ The pair "$(A,B)$" for one or two cells is slightly inaccurate, so we want to avoid $(A_c,B_c)=(A_d,B_d)$ for two different cells $c=ij$ and $d=i'j'$? And which are the own trials to solve the puzzle?! $\endgroup$
    – dan_fulea
    Jul 17, 2019 at 16:39
  • $\begingroup$ It is some permutation of indexes with no fix point, you can do that by iterating cycles for each raw $\endgroup$
    – Toni Mhax
    Jul 17, 2019 at 16:40
  • 1
    $\begingroup$ @ToniMhax I have written a computer code to check this numerically. I have high suspicion that there are no solutions for N=4 and N=10, but I get a correct solution for N=3. That is why I ask $\endgroup$ Jul 17, 2019 at 16:43
  • $\begingroup$ @dan_fulea I believe that point 5 is sufficiently clear. All cells must have a different pair written in them, so there are no two cells that would have the same pair. Can you elaborate why you believe point 5 is inaccurate? My own attempt was to apply a bunch of permutations on paper for N=10, it did not work, then to write a computer code, it also did not find a solution. I have no idea why for some $N$ there exist solutions and for other's there do not. Maybe my code is wrong, I can post if it helps, but it is brute force search, so hard to screw that up :) $\endgroup$ Jul 17, 2019 at 16:46
  • 2
    $\begingroup$ I believe this is known as a Graeco-Latin Square. It is known that the only values for N where a solution does not exist are 2 and 6. Wikipedia $\endgroup$ Jul 17, 2019 at 17:32

1 Answer 1

1
$\begingroup$

This is known as a Graeco-Latin Square. The only values for $N$ that do not have a solution are 2 and 6. Here is the wikipedia article for it:

Graeco-Latin Squares

There is also a proof for the non-existence of a solution for $N=6$ here:

Proof of non-existence for the $N=6$ case

$\endgroup$

You must log in to answer this question.

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