Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A magic square of order $n$ is an $n \times n$ grid containing each of the numbers $1,2,\dots,n^2$, so that the numbers in each row, column, and diagonal sum to the same number $n(n^2+1)/2$.

This question follows on from Is half-filled magic square problem NP-complete? about completing a partially filled magic square.

For $n=3$ the middle square must be $5$, so if the middle square is set to another value then there is no way to complete the magic square. On the other hand, if $n=4$ and a single number is specified (anywhere in the grid), then there is always a way to complete the magic square. This can be checked by inspection of the list of order-4 magic squares, from the site of Harvey Heinz.

Let $f(n)$ be the smallest number of values that when placed in an $n\times n$ grid, results in an pattern that cannot be completed to form a magic square. By the previous two examples, $f(3) = 1$ and $f(4) \ge 2$. The value $f(n)$ can also be thought of as the least number of values required in a partial $n \times n$ magic square for the decision problem to be interesting.

This motivates the question:

What is the asymptotic behaviour of $f(n)$ as $n$ tends to infinity?

I would be especially interested in knowing whether $f(n) = O(\log n)$, or if $f(n) = \Omega(n)$ (using big-O notation).

Consider the $k$ smallest numbers specified together with the $n-k$ largest numbers in the same row. This will fail to reach $n^2(n-1)/2$ when $k \gt n/2$. It then follows that $1 \le f(n) \le \lceil (n+1)/2 \rceil$. Are there sharper upper and lower bounds on $f(n)$, perhaps by distinguishing the case of $n$ even from $n$ odd?

share|improve this question

1 Answer 1

I have an idea which may lead to a proof that $f(n) = \Omega(\sqrt{n})$, but it would require quite a bit of work to flesh out.

Here is the idea: Take $n = m^2$. We are going to try to divide the n x n magic square into $m^2$ smaller m x m squares in such a way that each of our m clues lies in a different square. (Or as close to that as we can get).

Specifically, we are looking for a permutation $\pi \in S_n$ such that $\pi(n-k) = n - \pi(k)$. We then define the (a,b)-subsquare to be the subset $[\pi(ma),\pi(ma+1)...\pi(ma+m-1)]$ x $[\pi(mb),\pi(mb+1),...\pi(mb+m-1)]$ of our original square for $a,b \in [0,...m-1]$. We point out that the numbers on the $x=y$ diagonal of the (a,a)-subsquare all came from the corresponding diagonal of the main square. Likewise, the numbers on the $x=m-1-y$ diagonal of the (a,m-1-a)-subsquare came from the other diagonal of the main square.

We next look for a way to divide the numbers from 1 to $n^2 = m^4$ in such a way as to make all $m^2$ subsquares into magic squares with the same sum. This is not possible for m even, but may be possible for m odd. We don't actually need that they have the same sum, just that the m x m matrix of sums is itself a magic square, with non-distinct entries -- this may help us in the case of even m. Once we've done this, we've solved the original magic square.

1) For any m-point subset S of $[0,...,n-1]^2$, is there a permutation $\pi$ such that $(\pi(a),\pi(b))$ is not in the same subsquare as $(\pi(c),\pi(d))$ for $(a,b),(c,d) \in S$?

2) Given such a permutation, is there a way to complete the $m^2$ subsquares into magic squares with the same sum using the numbers from 1 to $m^4$?

share|improve this answer
1  
A good idea. Down a similar line, you could partition the numbers from 1 to n^2 into blocks of m^2, then make a magic square of magic squares. There are also permutations available mulitplying each number by a something coprime to n (mod n^2). –  Ross Millikan Sep 1 '11 at 15:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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