11
$\begingroup$

Imagine an $n \times n$ grid filled with the numbers 1, ..., $n$ where $n$ > 3 each number appearing n times, where each row, column, and diagonal all equal the same number. Can you fill grid like this? If so, show an example, and include as much detail as possible (for example if there's only 1 solution). If not, provide mathematical proof it's impossible.

I've purposely excluded $1 \times 1$ due to simplicity, $2 \times 2$ due to impossibility and $3 \times 3$ also due to impossibility (for solvers like you!)

$\endgroup$
4
  • 3
    $\begingroup$ Do you mean the rows, columns, and diagonals have the same sum? $\endgroup$ Dec 18, 2014 at 17:04
  • $\begingroup$ $3\times 3$ is not possible either (place the different elements on the diagonal, and you cannot use any element on the off-diagonal) You might want to rephrase that bit in your question. $\endgroup$
    – M.Herzkamp
    Dec 19, 2014 at 10:43
  • $\begingroup$ In the spirit of this site, I think Julian's answer it's the best and should be the accepted one. $\endgroup$
    – BmyGuest
    Dec 20, 2014 at 8:17
  • $\begingroup$ @BmyGuest I cannot accept Julian's answer as it does not fully answer the question. $\endgroup$
    – warspyking
    Dec 20, 2014 at 15:04

6 Answers 6

8
$\begingroup$

Nice idea for a puzzle, reminds me of Sudoku in a way. An answer for 4x4 (Simple I know but I have to start somewhere):

4x4 Image

How I found it:

If the total of each row, column and diagonal must be the same, then it follows that the total for an $n$ x $n$ square must be $n^2 /2 + n/2$. This is achieved with one of each of the numbers $1, ... n$ appearing in every row, column and diagonal.

To find my answer, I started by filling in a diagonal with numbers 1-4, then simply filled in the remainder through trial and error.

Fear not, more answers will come! I extended the method I used for 4x4 and solved the 5x5 this time:

5x5 Image
This time I started again by filling in the diagonal, but then filled in the 3s in a symmetrical pattern. After that I filled in the 1s and then rotated that design by 180 degrees and used it again for the 5s. Lastly I solved the 2s and 4s in the same way.

So, to summarise:

Filling a $n \times n$ grid with the above rules seems to always be possible, because as pointed out by squeamish ossifrage, there are hundreds of thousands of permutations for the numbers to sit in for the 9x9.

$\endgroup$
10
  • $\begingroup$ Nice, I look forward to 6, 7, 8, and 10 (9 can be included but already solved by someone else) $\endgroup$
    – warspyking
    Dec 18, 2014 at 13:50
  • $\begingroup$ Thanks, already working on 9 so I'll finish it quickly. I guess the real puzzle is finding an infallible method for any nxn (excluding 2 of course) $\endgroup$ Dec 18, 2014 at 13:52
  • $\begingroup$ On second thought, maybe I'll leave nine... after filling the whole thing in I just realised I messed up the 1s and 9s :( $\endgroup$ Dec 18, 2014 at 14:04
  • 2
    $\begingroup$ 3×3 is basic? Impossible more like. Whatever permutation of 1, 2 and 3 you have on the top row, one of them will always be repeated in the middle cell, making it impossible to obtain a total of 6 in every row & column and on both diagonals. $\endgroup$
    – r3mainer
    Dec 18, 2014 at 14:08
  • 1
    $\begingroup$ @ForIInRange I (maybe wrongly) interpreted the question to mean all the rows, cols, and diags have to add to the same number. I agree with you in that I think the puzzle is more interesting if they all must contain each number exactly once. $\endgroup$
    – Lopsy
    Dec 18, 2014 at 17:44
16
$\begingroup$

The squares you describe are related to Latin squares. A Latin square of order $n$ is an $n\times n$ square grid, filled with the numbers $1,\ldots,n$, such that each number appears once in every row and in every column. A Latin square is called doubly diagonal if each number also appears once on each diagonals. A doubly diagonal Latin square satisfies your condition, because each number appears $n$ times, and the rows, columns, and diagonals sum to $1+\ldots+n=\frac{n(n+1)}{2}$.

For $n$ a positive integer, a doubly diagonal Latin square of order $n$ exists if and only if $n=1$ or $n\geq 4$. I won't try to describe the general construction here, but this is written down explicitly in [1].

[1] Gergely, Ervin. A simple method for constructing doubly diagonalized Latin squares. J. Combinatorial Theory Ser. A, 16 (1974), 266--272.

$\endgroup$
3
  • $\begingroup$ I would expect this answer to become the accepted one, as it is a fully complete answer reducing the problem to an existing one with already known answer. $\endgroup$
    – BmyGuest
    Dec 20, 2014 at 8:16
  • $\begingroup$ @BmyGuest It really is a better answer. Mine was first but this is a more comprehensive answer $\endgroup$ Dec 27, 2014 at 16:55
  • 1
    $\begingroup$ My question got upvoted which caused me to come back. The reason I never accepted this was because you never provided an example "Can you fill grid like this? If so, show an example, and include as much detail as possible" $\endgroup$
    – warspyking
    Jun 27, 2015 at 0:19
8
$\begingroup$

I found a simple algorithm for odd numbers not divisible by 3.

Start with 1,2,...,n
For each subsequent row, push by 2.

5x5:

1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4
3 4 5 1 2

7x7:

1 2 3 4 5 6 7
6 7 1 2 3 4 5
4 5 6 7 1 2 3
2 3 4 5 6 7 1
7 1 2 3 4 5 6
5 6 7 1 2 3 4
3 4 5 6 7 1 2

11x11:

1  2  3  4  5  6  7  8  9  10 11
10 11 1  2  3  4  5  6  7  8  9
8  9  10 11 1  2  3  4  5  6  7
6  7  8  9  10 11 1  2  3  4  5
4  5  6  7  8  9  10 11 1  2  3
2  3  4  5  6  7  8  9  10 11 1
11 1  2  3  4  5  6  7  8  9  10
9  10 11 1  2  3  4  5  6  7  8
7  8  9  10 11 1  2  3  4  5  6
5  6  7  8  9  10 11 1  2  3  4
3  4  5  6  7  8  9  10 11 1  2

edit: See Lopsy's comment.

This method will work for any number not divisible by 2 or 3. If each column is a series with a push-value of p, each diagonal will be a series with a push-value of p-1 and p+1. At 2, this means one diagonal is pushed by 1 (1,n,n-1,...,2), or pushed by 3.

So as long as a number does not share any divisors with p-1,p, or p+1, and p is not equal to 1 or n-1, p should work for that n.

This is equivalent to the classical algorithm for generating Latin squares (pushing by 1 each row), then taking out the even rows and appending them to the bottom.

I'm sure it's always possible to build these squares for n > 3, but this is just an easy case for these numbers.

$\endgroup$
1
  • 3
    $\begingroup$ This construction works not just for primes, but for any number not divisible by 2 or 3. $\endgroup$
    – Lopsy
    Dec 18, 2014 at 19:02
4
$\begingroup$

Here's a $9 \times 9$ grid that I found in about a minute using a Sudoku solver:

1 7 5 3 9 4 8 2 6
4 2 6 1 8 7 3 9 5
8 9 3 6 2 5 1 4 7
7 5 2 4 1 8 9 6 3
3 6 1 2 5 9 4 7 8
9 4 8 7 3 6 5 1 2
5 8 4 9 6 2 7 3 1
6 3 9 5 7 1 2 8 4
2 1 7 8 4 3 6 5 9

There are thousands more $9 \times 9$ solutions. From this square alone, I think it's possible to generate another 2903039 possible answers (since there are 9! permutations of the numbers 1-9, and the grids can be rotated four different ways with two possible reflections).

$\endgroup$
4
$\begingroup$

Let me trump the others (for now) with a 16x16: (taken from my answer to another question here:

here

Given each line (and each main diagonal) holds numbers 1-16, they all have a total value of 136. Each number also appears 16 times.

As a bonus: it's a working 16x16 sudoku, with each 4x4 block being a magic square.

$\endgroup$
0
$\begingroup$

There seems to be multiple interpretations of this question.

Every broken diagonal contains every symbol

Possible if and only if $n$ is odd.

We can use diagonally cyclic Latin squares (as in DrLemniscate's answer). For all odd $n \geq 1$, we use this particular square: $$ \begin{bmatrix} \color{blue} 8 & 7 & 6 & 5 & 4 & \color{red} 3 & 2 & 1 & 0 \\ 1 & \color{blue}0 & 8 & 7 & 6 & 5 & \color{red} 4 & 3 & 2 \\ 3 & 2 & \color{blue} 1 & 0 & 8 & 7 & 6 & \color{red} 5 & 4 \\ 5 & 4 & 3 & \color{blue} 2 & 1 & 0 & 8 & 7 & \color{red} 6 \\ \color{red} 7 & 6 & 5 & 4 & \color{blue} 3 & 2 & 1 & 0 & 8 \\ 0 & \color{red} 8 & 7 & 6 & 5 & \color{blue} 4 & 3 & 2 & 1 \\ 2 & 1 & \color{red} 0 & 8 & 7 & 6 & \color{blue} 5 & 4 & 3 \\ 4 & 3 & 2 & \color{red} 1 & 0 & 8 & 7 & \color{blue} 6 & 5 \\ 6 & 5 & 4 & 3 & \color{red} 2 & 1 & 0 & 8 & \color{blue} 7 \\ \end{bmatrix} $$ Horizontally the symbols decrease by $1$; vertically the symbols increase by $2$; along the main broken diagonals (and in particular, along the main diagonal) the symbols increase by $1$. These properties ensure that there are no repeated symbols in rows and columns (i.e., it is a Latin square), and there are no repeated symbols on the broken diagonals. (Formally, $-1$, $1$, and $2$ are generators of $\mathbb{Z}_n$ when $n$ is odd.)

Now at this point we notice that diagonally cyclic Latin squares have an orthogonal mate where each main diagonal is a unique symbol: $$ \begin{bmatrix} \color{blue} 2 & \color{red} 1 & \bf \color{green} 0 \\ \bf \color{green} 1 & \color{blue} 0 & \color{red} 2 \\ \color{red} 0 & \bf \color{green} 2 & \color{blue} 1 \\ \end{bmatrix} \begin{bmatrix} \color{blue} 0 & \color{red} 1 & \bf \color{green} 2 \\ \bf \color{green} 2 & \color{blue} 0 & \color{red} 1 \\ \color{red} 1 & \bf \color{green} 2 & \color{blue} 0 \\ \end{bmatrix}. $$ However, the cyclic Latin square (generalizing the Latin square on the right above) has no orthogonal mate when $n$ is even (this goes back to Euler), so the desired Latin square impossible when $n$ is even.

Every broken diagonal and every broken antidiagonal contain every symbol

Possible if and only if $n \equiv \pm 1 \pmod 6$.

Since these are a special case of the previous case, they can only exist when $n$ is odd.

The diagonally cyclic Latin squares in DrLemniscate's answer work when $n \equiv \pm 1 \pmod 6$: along the main broken diagonals (and in particular, along the main diagonal) the symbols increase by $3$ (since $3$ generates $\mathbb{Z}_n$ in these cases).

When $n \equiv 3 \pmod 6$, it wasn't immediately obvious so I asked about it on MathOverflow. Afterwards, I realized it would give rise to a "strong complete mapping" and they don't exist when $n \equiv 3 \pmod 6$.

The main diagonal and the main antidiagonal contain every symbol

Possible if and only if $n \not\in \{2,3\}$.

Here, no conditions are applied to the non-main broken diagonals and antidiagonals. These are called doubly diagonal Latin squares. Julian Rosen's answer covers this, although there were other proofs around the same time:

A. J. W. Hilton, On double diagonal and cross latin squares,J. London Math, 1973 (link).

C. C. Lindner, On constructing doubly diagonalized latin squares, Feriodica Mathematica Hungarica Vol. 5 (3), (1974), pp. 249--253 (link).

You're unlikely to get a better write-up of the general case than the published papers on this. However, we've basically already solved a large number of cases.

If we have two doubly diagonal Latin squares of orders $n$ and $m$ and take their direct product (if $L_{ij}$ and $M_{ij}$ are the Latin squares, than its direct product is a new Latin square with $(L_{ij},M_{ij})$ in cell $(i,j)$), we get a doubly diagonal Latin square of order $nm$.

The diagonally cyclic Latin square construction when $n \equiv \pm 1 \pmod 6$ works here (which includes all primes $\geq 5$). And Hilton (op. cit.) gives these examples for orders $n \in \{4,6,8,9\}$.

Doubly diagonal Latin squares of orders 4,6,8,9.

So this is enough for when $n$ is not $2P$ or $3P$ where $P$ is a product of (not necessarily distinct) primes $\geq 5$. These cases seem to require more care, so it's best to refer to these papers.

The main diagonal contains every symbol

Possible if and only if $n \neq 2$.

I include this mostly for completeness sake. We take a diagonally cyclic Latin square of odd order $\geq 3$, and prolong it using a broken diagonal other than the main diagonal.

$$ \begin{bmatrix} 4 & \color{blue} 3 & 2 & 1 & 0 \\ 1 & 0 & \color{blue} 4 & 3 & 2 \\ 3 & 2 & 1 & \color{blue} 0 & 4 \\ 0 & 4 & 3 & 2 & \color{blue} 1 \\ \color{blue} 2 & 1 & 0 & 4 & 3 \\ \end{bmatrix} \longrightarrow \begin{bmatrix} 4 & \color{blue} 5 & 2 & 1 & 0 & \color{red} 3 \\ 1 & 0 & \color{blue} 5 & 3 & 2 & \color{red} 4 \\ 3 & 2 & 1 & \color{blue} 5 & 4 & \color{red} 0 \\ 1 & 4 & 3 & 2 & \color{blue} 5 & \color{red} 1 \\ \color{blue} 5 & 2 & 0 & 4 & 3 & \color{red} 2 \\ \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{red} 0 & \color{red} 1 & \color{red} 5 \\ \end{bmatrix} $$

When we prolong, we shift the contents of the chosen broken diagonal to both (a) a newly created column on the right, and (b) a newly created row at the bottom; fill the cells of the chosen broken diagonal with a new symbol; and add the new symbol to the bottom-right cell.

$\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.