Do there exist associative sudoku squares? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:24:51Z http://mathoverflow.net/feeds/question/39751 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39751/do-there-exist-associative-sudoku-squares Do there exist associative sudoku squares? cfranc 2010-09-23T13:57:42Z 2010-09-24T18:05:54Z <p>Last night I taught an algebra tutorial, and while writing out the multiplication table for the units of $\mathbb{Z}/5\mathbb{Z}$, a student remarked that it looked like a sudoku puzzle. I noted that it was similar, as the rows and columns all satisfy the sudoku condition, however the 2 by 2 sub-squares do not. The reason I gave is that multiplication is commutative in this group, and so the squares along the diagonal are symmetric. Afterwards I realized that there is an even simpler reason which excludes the possibility of nonabelian groups having multiplication tables which are sudoku squares: the identity element always messes up one of the sub-squares along the diagonal. This leads to the natural question: <em>do there exist associative sudoku squares of side length $n^2$</em>? (Meaning interpret the sudoku square as defining a binary operation on the integers $1$ through $n^2$. Is this binary operation ever associative? Of course I care about when $n > 1$ as $n = 1$ is clear.)</p> http://mathoverflow.net/questions/39751/do-there-exist-associative-sudoku-squares/39755#39755 Answer by Fiktor for Do there exist associative sudoku squares? Fiktor 2010-09-23T14:13:24Z 2010-09-24T18:05:54Z <p>If we are not obligated to keep the same order in rows and columns of the table, the answer is yes, and the group can be chosen to be commutative. For example the group $G=\left(\mathbb{Z}/(n\mathbb{Z})\right) ^{\times2}$,<br> the order of columns: $(1,1), (1,2), \dots, (1,n), (2,1), \dots, (n,n)$,<br> the order of rows: $(1,1), (2,1), \dots, (n,1), (1,2), \dots, (n,n)$.</p> <p>Otherwise, the answer is no for any $n>1$, because in any table of this type both $a\cdot 1$ and $1\cdot a$ are in the same $n\times n$ square for some $a\in G$.</p> <p><strong>Edit:</strong> If this operation doesn't need to define a group, then the answer is no too. Here is the proof.<br> Suppose $G$ is $\{1,\dots,n^2\}$ endowed with some associative operation and suppose, that the table of this operation is a sudoku table. Take any $x\in G$. In $x$-th line of the table we can find element $x$. Therefore $xy=x$ for some $y\in G$. Then take $a\in G$, such that $a\neq y$ and $ay$ and $ya$ are in the same square of the table. We have $(xy)a=x(ya)$ and, therefore $xa=x(ya)$. Using, that there is only one place in $x$-th line of the table, where we can find $xa$, we see that $a=ya$. From this we have $a(ya)=(ay)a$, $aa=(ay)a$ and $a=ay$. Therefore $ay=a=ya$ and the table is not a sudoku table.</p>