Open Problems Group: Open Problem #2

Original discussion: Open Problem #2

A magic square contains positive consecutive integers starting from 1 such that the rows, columns, and diagonals all add to the same value.

a 3 by 3 magic square

A heterosquare contains positive consecutive integers starting from 1 such that the rows, columns, and diagonals all add to different values.

If the sums resulting from a heterosquare form a consecutive sequence, the heterosquare is also called an antimagic square. (In the example above, if the sums of 9 and 24 were 16 and 17 instead, it would be a antimagic square.)

Prove that there are no 3 by 3 antimagic squares.

A related (but likely more difficult) open problem: "Does an \( n \times n \) antimagic square exist for all \( n > 3 ?\)"

The answer is thought to be "yes" but nobody knows for sure.

This problem, fortunately, lent itself well to a group approach. The collaboration was relatively spontaneous; people started chipping away at various cases with different approaches. People took ideas that eliminated some cases and expanded them to eliminate even more cases.

Key observations included focusing on combinations of sums of lines (leading to eliminating cases by algebra) and noticing an odd/even relationship with the diagonals.

The steps for the paper are as follows:

1. Determine the possible sums of the lines.
2. Determine the possible diagonal values.
3. Determine the possible center number.
4. Determine the possible outer row + outer column values.
5. Determine the possible combinations of values of the middle cells.
6. Show that for the remaining cases, the combinations do not yield at least one of the line sums that we need.

A current draft of the raw paper (in PDF format) is at the link here. Some of the arguments in the paper have been tightened up, but the wiki below conveys the arguments in the fashion that they were found.

The table below summarizes our results:

\( \begin{array} { c | c | c | c| c | c }
\text{Smallest Sum} & \text{Diag. Values} & \text{Center} & \text{Mid. Sums} & \text{ Mid. Values} & \text{Outer R/C Sums} & \text{ Outer R/C Values} & \text{ Elimination} \\ \hline \leq 10 & & & & & & & \text{Diagonal sums are too large } \\ \hline 11 & (11, 15) & 2 & 25 & (12, 13) & (32, 33) & (14, 18), (16, 17) & \text{Eliminated as individual case} \\
& & 3 & 28 & (12, 16) & (29, 33) & NA & \text{No possible outer row + column values} \\ & & 4 & 31 & (13, 18) & (27, 32) & NA & \text{No possible outer row + column values} \\ & & 4 & 31 & (14, 17) & (28, 31) & (12, 16), (13, 18) & \text{Eliminated as individual case} \\ & & 5 & 34 & (16, 18) & (27, 29) & (13, 14), (12, 17)& \text{Eliminated as individual case} \\
\hline 12 & (15, 19) & 5 & 26 & (12, 14) & & & \text{Eliminated as individual case} \\ & & 6 & 29 & (12, 17) & & & \text{Eliminated as individual case} \\ & & 6 & 29 & (13, 18) & (20,25) & NA & \text{No possible outer row + column values}\\ & & 7 & 32 &(13, 18) & (19,23) & NA & \text{No possible outer row + column values} \\ & & 8 & 35 & (17, 18) & & & \text{Eliminated as individual case} \\ \hline
\geq 13 & & & & & & & \text{Diagonal sums are too small } \\ \hline \end{array} \)

The sums are in consecutive sequence, and we first conclude the starting value has to be either 11 or 12, eliminating all cases where this doesn't happen. We then do some algebra on the outer row and column values of the 3 x 3 square to eliminate several more of the cases. This leaves 6 more cases that we eliminate individually.

From Mike Harding and Steven Jim:

For 3 by 3 antimagic squares, the only plausible sequences of sums are the following:

• 11, 12, 13, 14, 15, 16, 17, 18 and
• 12, 13, 14, 15, 16, 17, 18, 19.

Let's label the squares in the 3 by 3 matrix like this:

\[ \begin{array}{c|c|c} a & b & c \\ \hline d & e & f \\ \hline g & h & i \\ \end{array} \]

Considering there are two diagonals, three verticals, and three horizontals, there are 8 numbers which must be consecutive in order for this to happen. Say \(n\) is the smallest of these numbers. The sum of these numbers is \(8n+28.\) We know that the sum must be at least \(106,\) since that is the sum of the rows, the columns, and the lowest possible sum for the diagonals.

Proving the sum of the sums must be less than \(135:\) The sum of the diagonals is \(a+c+2e+g+i.\) To prove that the sum must be less than \(135,\) we need to prove that that is less than \(45\) which is the sum of all 9 letters \(a\) through \(i.\) Canceling numbers that appear on both sides, we must prove that \(e\) must be less than \(b+d+f+h.\) Conveniently, none of the nine letters are the same and are all positive integers less than or equal to \(9.\) Thus \(9\) is the largest possible value for \(e.\) The smallest sum of four letters possible is \(10.\) Thus \(e < b+d+f+h.\) So the sum of all eight sums must be less than \(135:\)

\[\begin{align} 106 \leq T &\leq 135\\ 106 \leq 8n+28 &\leq 135\\ 78 \leq 8n &\leq 107. \end{align}\]

Since \(n\) is an integer, we know that \(80 \leq 8n \leq 104\implies 10 \leq n \leq 13.\)

If \(a + c + 2e + g + i \leq 20,\) either \(a + e + i \leq 9\) or \(c + e + i \leq 9\) is true, which means \(T \geq 111\), which in turn means \(n \geq 11.\)

\(n\) can't be equal to \(13,\) as we can see that the sum of the two diagonals then will be \(132 - 90 = 42 > 20 + 19\).

Therefore, \(11 \leq n \leq 12\), which means only the following two sequences are possible:

• 11, 12, 13, 14, 15, 16, 17, 18 and
• 12, 13, 14, 15, 16, 17, 18, 19. \(_\square\)

From Stefan van der Waal:

For a 3 by 3 antimagic square, neither of the diagonals can have an even sum.

As in previous work, we use the following naming scheme:

\[ \begin{array}{c|c|c} a & b & c \\ \hline d & e & f \\ \hline g & h & i \\ \end{array} \]

From previous work, we know the following:

• We need to place the number 1, 2, 3, ..., 9. Five of these numbers are odd and four are even
• The combined sum of all the rows, all the columns, and the two diagonals must add up to either 116 or 124. These are both even numbers.
• Of the eight sums for the rows, columns, and diagonals, four must be even, and the other four odd.

Since the combined sum of all rows, columns, and diagonals must be even, we can calculate the following:

\[\begin{align} &(a + b + c) + (d + e + f) + (g + h + i) + (a + d +g) + (b + e + h) + (c + f + i) + (a + e + i) + (c + e + g) \\\\ &= 3a + 2b + 3c + 2d + 4e + 2f + 3g + 2h + 3i \\\\ &\equiv a + c + g + i \equiv 0\ (\textrm{mod}\ 2). \end{align} \]

So \( a + c + g + i\), the sum of all the corners, must be equal to some even number. The only way that's true is if exactly 0, exactly 2, or exactly 4 of the corners are odd. Let's look at all these cases and check if it's possible to have at least one diagonal with an even sum.

Case 1: None of the corners are odd.

In this case, the four even numbers must all go into the corners, and the five odd numbers go in the remaining spots. This leads to the following 3 x 3 matrix, where 1 means 'some odd number' and 0 means 'some even number':

\[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}. \]

The sums of both diagonals are odd, so in this case it's impossible to have at least one even diagonal.

Case 2: All 4 corners are odd.

If all corners are equal to an odd number and at least one diagonal must be equal to some even number, the center must be some even number. Due to rotational symmetry, it doesn't matter where the last odd number gets placed. This leads to the following 3 x 3 matrix:

\[ \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}. \]

This matrix has 2 even rows, 2 even columns, and 2 even diagonals. The remaining 2 sums are odd. This isn't equal to the required 4 even and 4 odd sums. Therefore case 2 also can't help us create an antimagic square with at least one diagonal with an even sum.

Case 3: Exactly 2 corners are odd.

There are two ways of placing 2 odd numbers in the corners. There are two ways of placing these odd numbers:

Case 3 sub-case 1: The odd numbers are opposite to each other.

To make sure there's at least one even diagonal, the center must have some even number. The 3 x 3 matrix now looks like this:

\[ \begin{bmatrix} 0 & ? & 1 \\ ? & 0 & ? \\ 1 & ? & 0 \end{bmatrix}. \]

Due to rotational and reflection symmetry, it doesn't matter where we place the fourth even number. So we might fill out the matrix entirely like this:

\[ \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}. \]

This matrix has 2 even rows, 2 even columns, and 2 even diagonals. The remaining 2 sums are odd. This isn't equal to the required 4 even and 4 odd sums. Therefore case 3 sub-case 1 also can't help us create an antimagic square with at least one diagonal with an even sum.

Case 3 sub-case 2: The odd numbers are adjacent to each other.

To make sure there's at least one even diagonal, the center must have some odd number number. The 3 x 3 matrix now looks like this:

\[ \begin{bmatrix} 1 & ? & 0 \\ ? & 1 & ? \\ 1 & ? & 0 \end{bmatrix}. \]

There are 4 ways of placing the remaining 2 even and 2 odd numbers, after taking out reflections:

\[ \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}. \]

The first matrix only has 2 even diagonals. The other 3 matrices have 2 even rows, 2 even columns, and 2 even diagonals. None of these are the required 4 even and 4 odd sums. Therefore case 3 sub-case 2 also can't help us create an antimagic square with at least one diagonal with an even sum.

Since all of the cases are dead ends, it's impossible to have a 3 x 3 antimagic square with at least one even diagonal. \(_\square \)

From Steven Yuan:

The possible values for pairs of diagonals and pairs of middles, as well as their corresponding values for \(e,\) are shown here:

\[ \begin{array}{c|c|c} \text{Diagonals} & \text{Middles} & e \\ \hline (11,15) & (12,13) & 2 \\ & (14,17) & 4 \\ & (16,18) & 5 \\ \hline (15,19) & (12,14) & 5 \\ & (13,16) & 6 \\ & (17,18) & 8 \end{array} \]

As usual, we label the squares as follows:

\[\begin{array}{c|c|c} a & b & c \\ \hline d & e & f \\ \hline g & h & i \\ \end{array}\]

As mentioned above, only two sequences are possible for a 3 x 3 anti-magic square: \(11, 12, ..., 18\) and \(12, 13, ..., 19.\) Let’s focus on the first possible "anti-magical" sequence. The sum of all the numbers in the sequence is equal to 116. This is equal to the combined sum of the numbers in the three rows, the numbers in the three columns, and the numbers in the two diagonals. Since both the union of all the rows and the union of all the columns is \({1, 2, ..., 9}\), their sum is equal to 45, and the diagonal sum is \((a + e + i) + (c + e + g) = 116 - 2(45) = 26 \).

Now, consider the sum of the numbers from the middle column and middle row (the "middle sums"). It’s equal to \((b + e + h) + (d + e + f).\) Summing this with the diagonal sum gives us

\[ (a + e + i) + (c + e + g) + (b + e + h) + (d + e + f) = (a + b + c + d + e + f + g + h + i) + 3e = 3e + 45. \]

Plugging in our value for the diagonal sum gives us \( (b + e + h) + (d + e + f) = 3e + 45 - 26 = 3e + 19. \)

There are only two pairs of distinct integers in the range \([11, 18]\) that sum to 26: \((11, 15)\) and \((12, 14).\) This means that one diagonal sums to one of the numbers in a pair, and the other diagonal sums to the other. We can assign a value to the middle sums by noting that it must be one more than a multiple of 3, since it's equal to \( 3e + 19 \equiv 1 \!\pmod{3} \). Here we must do some casework:

• If we chose \((11, 15)\) for the diagonals, we are left with 12, 13, 14, 16, 17, 18 for the middle sums. We must choose two integers that sum to a number that is two more than a multiple of three. This means the possible middle sums are \( (12, 13), (12, 16), (13, 18), (14, 17), (16, 18).\)

• If we chose \((12, 14)\) for the diagonals, we are left with 11, 13, 15, 16, 17, 18 for the middle sums. Using the same criteria as in the previous case, the possible middle sums are \( (11, 17), (13, 15), (13, 18), (15, 16), (16, 18). \)

For each possible middle sum pair, we can find the value of \(e,\) i.e. the middle number by using middle sum = \(3e + 19.\) For example, if we chose \((11, 15)\) for the diagonals and \((14, 17)\) for the middles, then \(e = \frac{14+17-19}{3} = 4.\) If we do this for every possible middle sum pair, we find that if there exists an anti-magic square whose sequence is 11 to 18, then the middle number \(e\) is between 2 and 5 inclusive.

Applying the same procedure to the sequence \(12, 13, ..., 19,\) we can conclude that \(e \in [5,8].\) in this case. The middle number cannot be 1 or 9.

The possible values for pairs of diagonals and pairs of middles, as well as their corresponding values for \(e\) are shown here:

\[ \begin{array}{c|c|c} \text{Diagonals} & \text{Middles} & e \\ \hline (11,15) & (12,13) & 2 \\ & (12,16) & 3 \\ & (13,18) & 4 \\ & (14,17) & 4 \\ & (16,18) & 5 \\ \hline (12,14) & (11,17) & 3 \\ & (13,15) & 3 \\ & (13,18) & 4 \\ & (15,16) & 4 \\ & (16,18) & 5 \\ \hline (15,19) & (12,14) & 5 \\ & (12,17) & 6 \\ & (13,16) & 6 \\ & (14,18) & 7 \\ & (17,18) & 8 \\ \hline (16,18) & (12,14) & 5 \\ & (12,17) & 6 \\ & (13,19) & 7 \\ & (14,15) & 6 \\ & (15,17) & 7 \end{array} \]

As mentioned above, the sums of the diagonals can't be even, so all of the \( (12, 14) \) and \( (16, 18) \) diagonal sum cases can be removed.

For each remaining case, we can calculate \( a + c + g + i, b + h, \) and \( d + f \) by subtracting \(2e\) from the diagonal sum and \(e\) from each individual middle sum. WLOG we can assume that the first number in each pair of middle sums equals \(b + e + h\) and the other equals \(d + e + f.\) To simplify the proceeding explanation, let's focus on one pair of diagonal and middle sums—\((11, 15)\) and \((13, 18).\) The corner number sum is

\[ a + c + g + i = 26 - 2e = 26 - 2(4) = 18 \]

and we also have

\[\begin{align} b + h = 13 - e = 13 - 4 &= 9 \\ d + f = 18 - e = 18 - 4 &= 14. \end{align} \]

Now we can use these values to calculate the sum of the "outer rows" \( (a + b + c) + (g + h + i) \) and the sum of the "outer columns" \( (a + d + g) + (c + f + i): \)

\[\begin{align} (a + b + c) + (g + h + i) = (a + c + g + i) + (b + h) = 18 + 9 &= 27 \\ (a + d + g) + (c + f + i) = (a + c + g + i) + (d + f) = 18 + 14 &= 32. \end{align} \]

The remaining sum values we haven't used yet for this case are 12, 14, 16, and 17. We must assign these values to the outer rows and columns such that the above relations are true. However, it is fairly easy to see that no assignment of these four integers to \( (a + b + c, g + h + i, a + d + g, c + f + i) \) will satisfy the above requirements. Thus, if an anti-magical square of order 3 exists, then the diagonal and middle sums cannot be \((11, 15)\) and \((13, 18),\) respectively.

We can use the above method on the other 9 possible cases, checking to see if we can assign the remaining sum values to the outer rows and columns. These four cases do not work out:

\[ \begin{array}{c|c|c} \text{Diagonals} & \text{Middles} & e \\ \hline (11,15) & (12,16) & 3 \\ & (13,18) & 4 \\ \hline (15,19) & (12,17) & 6 \\ & (14,18) & 7 \end{array} \]

The other six have valid sum value assignments, so we would have to directly check them to verify that they don't work. These are

\[ \begin{array}{c|c|c} \text{Diagonals} & \text{Middles} & e \\ \hline (11,15) & (12,13) & 2 \\ & (14,17) & 4 \\ & (16,18) & 5 \\ \hline (15,19) & (12,14) & 5 \\ & (13,16) & 6 \\ & (17,18) & 8 \end{array} \]

From Stefan van der Waal:

Here are the last 6 cases Steven Yuan presented:

\[ \begin{array}{c|c|c} \text{Diagonals} & \text{Middles} & e \\ \hline (11,15) & (12,13) & 2 \\ & (14,17) & 4 \\ & (16,18) & 5 \\ \hline (15,19) & (12,14) & 5 \\ & (13,16) & 6 \\ & (17,18) & 8 \end{array} \]

As usual, we use the following naming convention:

\[ \begin{array}{c|c|c} a & b & c \\ \hline d & e & f \\ \hline g & h & i \\ \end{array} \]

Case 1: diagonals (11, 15) and middle sums (12, 13)

In this case, \(e\) is 2. If we subtract \(e\) from all the diagonals and middles and look at all the ways we can add up two of the remaining 8 digits to get those remainders, we get the following options:

\[ \begin{array}{c|c|c|c} \text{Diagonal 1:9} & \text{Diagonal 2:13} & \text{Middle 1:10} & \text{Middle 2:11} \\ \hline (1,8) & (4, 9) & (1, 9) & (3, 8) \\ (3, 6) & (5,8) & (3, 7) & (4, 7) \\ (4, 5) & (6,7) & (4, 6) & (5, 6) \end{array} \]

We must select one option from every column, and we need to select every digit exactly once. There are three ways to do that:

\[ \begin{array}{c|c|c|c} \text{Diagonal 1:9} & \text{Diagonal 2:13} & \text{Middle 1:10} & \text{Middle 2:11} \\ \hline (1,8) & (4, 9) & (3, 7) & (5, 6) \\ (3, 6) & (5,8) & (1, 9) & (4, 7) \\ (4, 5) & (6, 7) & (1, 9) & (3, 8) \end{array} \]

To create an antimagic square, the outer sums \((a + b + c)\), \((g + h + i)\), \((a + d + g)\), and \((c + f + i)\) must add up to the remaining four sums: 14, 16, 17, and 18. For every sum, we need to pick exactly 1 digit from every diagonal and exactly 1 digit from one of the middles.

Now try to make 14 by picking exactly one digit from each diagonal and one from a middle sum for the first option. It becomes quickly clear that it's not possible to do that. It's also not possible to make 14 with the second option. It is possible to do in the third option \((4 + 7 + 3 = 14)\), but it's impossible to create a 16 with the third option. Therefore, the first case \((11, 15)\) for the diagonals and \((12, 13)\) for the middle sums won't work.

Case 2: diagonals (11, 15) and middle sums (14, 17)

In this case, \(e\) is 4. Again, the ways to add up the remaining digits to get the sums are as follows:

\[ \begin{array}{c|c|c|c} \text{Diagonal 1:7} & \text{Diagonal 2:11} & \text{Middle 1:10} & \text{Middle 2:13} \\ \hline (1,6) & (2, 9) & (1, 9) & (5, 8) \\ (2, 5) & (3,8) & (2, 8) & (6, 7) \\ & (5,6) & (3, 7) & \end{array} \]

The two ways to select one from each column, together with the reason why each case won't work, are as follows:

\[ \begin{array}{c|c|c|c|c} \text{Diagonal 1:9} & \text{Diagonal 2:13} & \text{Middle 1:10} & \text{Middle 2:11} & \text{Reason it won't work} \\ \hline (2,5) & (3, 8) & (1, 9) & (6, 7) & \text{Impossible to make 13} \\ (1, 6) & (2,9) & (3, 7) & (5, 8) & \text{Impossible to make 12} \end{array} \]

Case 3: diagonals (11, 15) and middle sums (16, 18)

In this case, \(e\) is 5, and there's only one way of selecting the digits:

\[ \begin{array}{c|c|c|c} \text{Diagonal 1:6} & \text{Diagonal 2:10} & \text{Middle 1:11} & \text{Middle 2:13} \\ \hline (2,4) & (1, 9) & (3, 8) & (6, 7) \end{array} \]

It's also possible to create all of the remaining sums: 12, 13, 14, and 17. For all of these numbers, there's only one way to make them, and when we look closer at the 12 and 13, it becomes clear why this case won't create an antimagic square:

\[\begin{align} 12 &= 4 + 1 + 7 \\ 13 &= 4 + 1 + 8. \end{align} \]

The sums for 12 and 13 are both trying to grab the 1 and 4 from the diagonals, but only one number is allowed to do that.

Case 4: diagonals (15, 19) and middle sums (12, 14)

In this case, \(e\) is 5, and there's only one way of selecting the digits:

\[ \begin{array}{c|c|c|c} \text{Diagonal 1:10} & \text{Diagonal 2:14} & \text{Middle 1:7} & \text{Middle 2:9} \\ \hline (1,9) & (6, 8) & (3, 4) & (2, 7) \end{array} \]

It's also possible to create all of the remaining sums: 13, 16, 17, and 18. For all of these numbers, there's only one way to make them, and when we look closer at the 13 and 16, it becomes clear why this case won't create an antimagic square:

\[\begin{align} 13 &= 1 + 8 + 4 \\ 16 &= 1 + 8 + 7. \end{align} \]

The sums for 13 and 16 are both trying to grab the 1 and 8 from the diagonals, but only one number is allowed to do that.

Case 5: diagonals (15, 19) and middle sums (13, 16)

In this case, \(e\) is 6. Similar to what was done in Case 2, we have the following:

\[ \begin{array}{c|c|c|c|c} \text{Diagonal 1:9} & \text{Diagonal 2:13} & \text{Middle 1:7} & \text{Middle 2:10} & \text{Reason it won't work} \\ \hline (2,7) & (5, 8) & (3, 4) & (1, 9) & \text{Impossible to make 12} \\ (1, 8) & (4, 9) & (2, 5) & (3, 7) & \text{Impossible to make 18} \end{array} \]

Case 6: diagonals (15, 19) and middle sums (17, 18)

In this case, \(e\) is 8. Similar to what was done in case 5, we have the following:

\[ \begin{array}{c|c|c|c|c} \text{Diagonal 1:7} & \text{Diagonal 2:11} & \text{Middle 1:9} & \text{Middle 2:10} & \text{Reason it won't work} \\ \hline (1,6) & (2, 9) & (4, 5) & (3, 7) & \text{Impossible to make 16} \\ (2, 5) & (4, 7) & (3, 6) & (1, 9) & \text{Impossible to make 14} \\ (3, 4) & (5, 6) & (2, 7) & (1, 9) & \text{Impossible to make 13} \end{array} \]

All 6 cases are impossible and therefore there is no 3 x 3 antimagic square. \(_\square\)