2
$\begingroup$

I'm trying to build a variation of a latin square.

In a latin square of size $n$, every row and every column contains a number from $1$ to $n$ exactly once. Given arbitrary $a$ and $b$ such that $n=a\cdot b$, I would like to build a size $n$ square where given an arbitrary row or column, it contains $b$ distinct numbers and each number appears exactly $a$ times. Additionally, any given number used in the square must appear exactly $n$ times in the entire square, as in the original latin square problem, except for the case where that number appears on the diagonal, in which case every diagonal occurrence is counted twice (with this counting the number of occurrences should be $n$ for every number). This means that the numbers are generally not the same across rows/columns for most values of $a,b$.

I would be particularly interested in the special case where the resulting square is symmetric.

Does anyone have any idea of how complicated the problem is (building a single instance of a latin square of size $n$ is trivial) and what previous work I could look at?

EDIT: As suggested by Jyrki Lahtonen, it is possible that the construction is not possible for arbitrary values of $a,b$. I'm mainly interested in cases where $a<b$, in particular the $b=a+1$ case, where $n$ allows it.

As an example, for $n=6,a=2,b=3$, you can build the following (symmetric) square: $$ \begin{array}{ccccccccc} 2&0&0&1&1&2\\ 0&4&0&3&4&3\\ 0&0&5&5&6&6\\ 1&3&5&5&1&3\\ 1&4&6&1&4&6\\ 2&3&6&3&6&2 \end{array} $$

$\endgroup$
  • $\begingroup$ Well, I never imposed any limit on the number of symbols, only said that should a symbol occur, then it has to occur $n$ times, where occurrences on the diagonal are counted twice. $\endgroup$ – bprs Jul 9 '14 at 8:24
  • $\begingroup$ Oh sorry, my mistake. I didn't see the extra diagonal condition. [I'll delete my comment.] $\endgroup$ – Rebecca J. Stones Jul 9 '14 at 8:31
  • $\begingroup$ Well my argument proving impossibility when $a> b$ may survive the rule change (diagonals counted twice), but has the question now converged in the sense that you will no longer change the question in an essential way? So far no harm done :-) $\endgroup$ – Jyrki Lahtonen Jul 9 '14 at 10:09
  • $\begingroup$ Yes, the question has converged. $\endgroup$ – bprs Jul 10 '14 at 7:08
1
$\begingroup$

You can take a normal Latin square and reduce each number modulo $a$

$\endgroup$
  • $\begingroup$ Your answer is correct for the original question I posted. I had forgotten to add a constraint, which was that any given number used in the square must appear exactly $n$ times, as in the original latin square problem. I updated the question to reflect this. $\endgroup$ – bprs Jul 9 '14 at 5:56
0
$\begingroup$

This is not an answer but an observation, as I cannot use TeX in comments.

Starting from your constraints, and trying to find something symmetric, I came up with this square which is strictly equivalent to yours (with permutation of coordinates and permutation of symbols).

I have to stress, that as in your example, there are 7 different symbols used for this 6x6 square. So that 36 = 3*(2+2)+4*(6). So on this account the similarity with latin squares is even more stretched.

$$ \begin{array}{cccccc} 1 & 1 & 4 & 5 & 4 & 5 \\ 1 & 1 & 0 & 6 & 6 & 0 \\ 4 & 0 & 2 & 2 & 4 & 0 \\ 5 & 6 & 2 & 2 & 6 & 5 \\ 4 & 6 & 4 & 6 & 3 & 3 \\ 5 & 0 & 0 & 5 & 3 & 3 \end{array} $$

Symbols having at least one member on the diagonal are grouped as squares. It would change from squares to other constellations with a different n=a*b

$$ \begin{array}{cccccc} \bf 1 &\bf 1 & 4 & 5 & 4 & 5 \\ \bf 1 &\bf 1 & 0 & 6 & 6 & 0 \\ 4 & 0 &\bf 2 &\bf 2 & 4 & 0 \\ 5 & 6 &\bf 2 &\bf 2 & 6 & 5 \\ 4 & 6 & 4 & 6 &\bf 3 &\bf 3 \\ 5 & 0 & 0 & 5 &\bf 3 &\bf 3 \end{array} $$

There is an interesting mix of periodicity and mirror symmetry in this result as in various constructions I tried.

For this particular square, the non-diagonal symbols appear as $4545/0660$, $4040/5665$ and $4646/5005$, i.e. as $abab/xyyx$

Latin squares have many interpretations. It would probably valuable to have at least one for your new combinatorial object. Perhaps do you have one already ?

$\endgroup$
  • $\begingroup$ I tried to come up with an alternative interpretation for the problem and I think I managed to do so in the form of a round-robin tournament problem. I'm still not sure that they are completely equivalent, so I asked for a solution to the problem in a separate question $\endgroup$ – bprs Jul 10 '14 at 7:11

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.