9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – 2012rcampion
    Commented Sep 20, 2016 at 0:51

1 Answer 1

Reset to default
7
$\begingroup$

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}$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Are there magic squares of any size? $\endgroup$
    – Matsmath
    Commented Sep 20, 2016 at 2:54
  • $\begingroup$ @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. $\endgroup$
    – Anon
    Commented Sep 20, 2016 at 3:01
  • 1
    $\begingroup$ Fair enough. I still suggest to include this in your answer. I myself assumed the existence of witchcrafts is common knowledge. $\endgroup$
    – Matsmath
    Commented Sep 20, 2016 at 3:07
  • 1
    $\begingroup$ 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$. $\endgroup$
    – 2012rcampion
    Commented Sep 20, 2016 at 4:15
  • 1
    $\begingroup$ 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}$$ $\endgroup$
    – Mike Earnest
    Commented Sep 20, 2016 at 17:19

Your Answer

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

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