# How big can a witchcraft square be?

A witchcraft square is defined to be an $n\times n$ square of distinct natural numbers such that the row sums and column sums form a set of $2n$ consecutive natural numbers. For example,

   5  11  14  15
8  13  10  17
9   2  22  16
24  21   4   3


is a witchcraft square because the row and column sums are $45, 46, 47, 48, 49, 50, 51, 52$ in some order.

For which values of $n$ does there exist an $n\times n$ witchcraft square?

This puzzle was created by Stanley Rabinowitz for the 1982-83 issue of the Journal of Recreational Mathematics. I don't know the answer.

• Well, for a start, it's only possible if you can partition the numbers from $1$ to $2n$ into two sets with the same total; which is only possible if the overall total, $(2n)(2n+1)/2=n(2n+1)$ is even, which is only true when $n$ is even. – 2012rcampion Sep 20 '16 at 0:51

As @2012rcampion said, this is only possible when $n$ is even: The sum of all row and column sums of a witchcraft square is the sum of $2n$ consecutive natural numbers, and if $n$ is odd, this sum contains an odd number of odd summands and is therefore odd itself. However the sum is also twice the sum of all matrix entries, so it must be even too. This is a contradiction.

So let's let $n$ be even. There exists a witchcraft square of size $n$, and this is how to construct one:

Consider this square $n\times n$ matrix:

$$A := \begin{pmatrix} 0&0&0&0&\cdots&1\\ 0&0&0&0&\cdots&4\\ 0&0&0&0&\cdots&5\\ 0&0&0&0&\cdots&8\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 2&3&6&7&\cdots&x \end{pmatrix}$$

Here the rightmost column, ignoring $x$, contains those numbers from $\{1, \ldots, 2n-2\}$ which leave a remainder of $0$ or $1$ modulo $4$, and the bottommost row contains all others.

Note that the right column sum is greater by $1$ than the bottom row sum, no matter the value of $x$. So let's choose $x \in \mathbb{Z}$ such that the sum of the values in the last column is $2n-1$ and the sum of the values in the last row is $2n$.

With this choice of $x$, $A$ is a witchcraft square up to the requirement that all entries are natural and distinct. To fix that, simply add a large multiple of any natural $n\times n$ magic square.

Example for $n = 4$:

$$\begin{pmatrix} 1200&100&1400&701\\ 1300&800&1100&204\\ 300&1000&500&1605\\ 602&1503&406&897 \end{pmatrix}$$

Note that there aren't any $2\times 2$ magic squares, so I'll add an explicit example for a $2\times 2$ witchcraft square (thanks @MikeEarnest):

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

• Are there magic squares of any size? – Matsmath Sep 20 '16 at 2:54
• @Matsmath The first paragraph shows that there are no magic squares of any odd size, the rest constructs a magic square of any even size. – Anon Sep 20 '16 at 3:01
• Fair enough. I still suggest to include this in your answer. I myself assumed the existence of witchcrafts is common knowledge. – Matsmath Sep 20 '16 at 3:07
• By the way, $x=\frac{7}{2}n-n^2-1$, meaning that you can choose any multiplier equal to or greater than $2n-2-\left(\frac{7}{2}n-n^2-1\right)+1=n^2-\frac{3}{2}n$. – 2012rcampion Sep 20 '16 at 4:15
• To be complete, here is a 2x2 witchcraft square (your construction technically doesn't cover this case, since there are no 2x2 magic squares). As a bonus, only Fibonacci numbers are used: $$\begin{pmatrix}3&1\\2&5\end{pmatrix}$$ – Mike Earnest Sep 20 '16 at 17:19