1
$\begingroup$

I can put the 6 combinations of ABC words in a 3x3 square

ABC = 3 letters = 6 combinations in a 3x3 square

enter image description here

For ABCD = 4 letters = 24 combinations in three 4x4 squares a solution was found by George Sicherman

enter image description here

Now can you find solutions for

ABCDE = 5 letters = 120 combinations in twelve 5x5 squares and

ABCDEF = 6 letters = 720 combinations in sixty 6x6 squares

If not, which is the most quantity of squares with different words you can find?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you aware of the answers to the questions you pose? Specifically, about whether solutions for ABCDE / ABCDEF exist, and/or what the optimal solutions are? If you know optimal solutions which don't use all of the combinations, are you aware of a proof of opimality? $\endgroup$
    – bobble
    Apr 21 at 1:15
  • 1
    $\begingroup$ I don´t know the answers. I think could exist perfect solutions for cases 5 and 6 as there are perfect solutions for cases 3 and 4 $\endgroup$
    – Rodolfo Kurchan
    Apr 21 at 1:25

2 Answers 2

Reset to default
1
$\begingroup$

Here's an explicit solution with $12$ squares for $n=5$, obtained via integer linear programming:

\begin{matrix}ABDEC&ACDEB&ABECD&AEBDC&ACBDE&ADBEC&ABCED&AEBCD&ADEBC&ABEDC&AEDCB&ADBCE&\\BAECD&BAEDC&EADBC&DACBE&DACEB&DAECB&CAEDB&CADBE&EADCB&EABCD&CABDE&CADEB&\\CDABE&DBACE&DCAEB&EBACD&CEABD&CBADE&DCABE&ECADB&CBAED&CDAEB&ECABD&BEADC&\\DECAB&CEBAD&BDCAE&CDEAB&EBDAC&BECAD&BEDAC&DBEAC&DCBAE&BCDAE&BDEAC&EBCAD&\\ECBDA&EDCBA&CEBDA&BCDEA&BDECA&ECDBA&EDBCA&BDCEA&BECDA&DECBA&DBCEA&DCEBA&\\\end{matrix}

I forced $A$ along the diagonals to heuristically reduce the search space.

Improve this answer
$\endgroup$
1
6
$\begingroup$

Based off your example for $n=4$, there should be an easy generalization for any $n\ge 3$, but I'll examplify using $n=5$ here.

Instead of letting the alphabet be $\{\mathrm{A,B,C,D,E}\}$, we instead use $\{0,1,2,3,4\}$ as they represent the 5 congruence classes of addition mod 5. Fix any two distinct permutations starting with $0$, say $(0,4,2,3,1)$ and $(0,2,4,3,1)$. For the addition table mod 5 using the two permutations as axes: \begin{array}{c|ccccc}+&0&4&2&3&1\\\hline0&0&4&2&3&1\\2&2&1&4&0&3\\4&4&3&1&2&0\\3&3&2&0&1&4\\ 1&1&0&3&4&2\\\end{array} Now notice that each row or column is the corresponding initial permutation but added some constant to all terms. But each permutation $\sigma$ of $\{0,1,2,3,4\}$ is uniquely formed by (a) taking a unique corresponding permutation starting with 0, and (b) adding a fixed value from $\{0,1,2,3,4\}$ and then mod 5 to all terms of the starting permutation. For example, \begin{equation}(2,3,1,0,4)\equiv(0,1,4,3,2)+2\pmod{5}\end{equation} Thus if we take all $(n-1)!$ many permutations starting with 0, group them into pairs, and form corresponding addition tables mod $n$, then we necessarily get each permutation on $\{0,\ldots,n-1\}$ precisely once. In particular, the optimal number of squares is equal to $\frac{(n-1)!}{2}$ for all $n\ge 3$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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