===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 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.

Want somewhere to start? Try solving this problem.


Unlike with Open Problem #1, this has been proven by computer brute force. The task here is to prove the result by something other than brute force. (The related question of if n n by n n antimagic squares exist for all n>3 n > 3 is entirely open.)

For the second Open Problem I wanted to emphasize the fact that mathematics doesn't just emphasize unknown pieces of knowledge; it also improves existing knowledge. A brute force proof doesn't give much insight into the nature of a mathematical structure, so a more elegant proof of the lack of 3 by 3 antimagic squares would be quite helpful for mathematicians working on the subject.


Since heterosquares are a superset of antimagic squares, one approach to this would be finding a systematic way of categorizing all heterosquares, and then looking for the special properties heterosquares that are not antimagic have.

Information about what antimagic squares look like in the larger cases would help understand the conditions for one to be made.

It's also possible to approach from the brute force computing end (even thought it's been done before) and work on ways of gradually improving the algorithm for identifying antimagic squares.

THERE IS A WIKI PAGE DEDICATED TO THE PROBLEM HERE


Some last comments (for now) on Open Problem #1:

Thanks for everyone who contributed! Our "final" wiki page giving results is here. I will be sharing this with the mathematician who originally wrote the problem (Erich Friedman) so there may be another update in the future!

Also, while the group effort will likely be focused on the current Open Problem, you are still welcome to work on the old one. Please label any posts that relate to an old Open Problem quite clearly so people don't get mixed up.

Note by Jason Dyer
3 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Introduction: For the sake of ease, let's label the squares positions a to i from the top left to the bottom right. 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 more than 90, since that is the sum without 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. Cancelling 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.

Inequalities: 90 < T < 135

90 < 8n+28 < 135

62 < 8n < 107

Since n is an integer, we know that 64 < 8n < 104

8 < n < 13

Conclusion: Based on the above calculations, we only need to worry about chains of 8 numbers with the starting number between 8 and 13 inclusively or

8, 9, 10, 11, 12, 13, 14, 15

9, 10, 11, 12, 13, 14, 15, 16

10, 11, 12, 13, 14, 15, 16, 17

11, 12, 13, 14, 15, 16, 17, 18

12, 13, 14, 15, 16, 17, 18, 19

13, 14, 15, 16, 17, 18, 19, 20

are the only possibilities.

Mike Harding - 3 years, 6 months ago

Log in to reply

Assume further that e=1, a=2, c=3, g=4, and i=5. Note that the diagonals add up to a+c+2e+g+i. 2+3+2+4+5=16. Thus 8n+28 must be greater than 90+16, or 106. Thus 8n must be greater than 78. So n must be greater than 9.75, so n must be greater than or equal to 10. So the first two cases are impossible.

Mike Harding - 3 years, 6 months ago

Amazing! Anyways, isn't it 8n138 \le n \le 13?

Also, if you add the sum of the diagonals, you fill find out that 8n+281068n+28\ge106, which means n10n\ge10. First two chains gone, right?

Also note that if a+c+2e+g+i20a+c+2e+g+i\le 20, either a+e+i9a+e+i\le9 or g+c+e9g+c+e\le9 is true (first two chains gone, which makes this an impossibility), which means T111T\ge111 or n11.n\ge11. The third one is gone too!

You can also eliminate the final chain, as we can see that the sum of the two diagonals then will be 13290=42>20+19132-90=42>20+19. Two to go. (Marcus' idea can be taken, although 10+11+12+13=46.10+11+12+13=46. At least 11+12+13+14=5011+12+13+14=50. Also, ee must be odd and ee can't be 9.)

Steven Jim - 3 years, 6 months ago

Log in to reply

Trying to compile into wiki page. Why can't e be even?

Mike Harding - 3 years, 6 months ago

Log in to reply

@Mike Harding Actually that was a mistake. I asked the other Steve, and he said his “proof” was invalid. So ee can be either even or odd

Steven Yuan - 3 years, 6 months ago

I've been thinking about Mike's solution for this whole afternoon, and it seems like I've found another way, which can be generalized for all nn, to reduce "the chain of numbers that we need to worry about" to 2.

(Details of detailed proof when k=3k=3 is in Mike Harding's comment, and is highly recommended for people who don't want to read the generalization.)

According to Mike's solution, in a k2k^2 square, there must be 2k+22k+2 consecutive values for the k2k^2 square to be anti-magic. Let nn be the smallest value, then the 2k+22k+2 consecutive values are n,n+1,...,n+2k+1n,n+1,...,n+2k+1, and the sum of those consecutive values are 2kn+2n+(2k+1)(k+1)2kn+2n+(2k+1)(k+1). The sum of the k2k^2 numbers inside is k2(k2+1)2\frac {k^2(k^2+1) }{2 }. Also, for a chain to be proved as incorrect, either (2k+1)nk2(k2+1)+(2k+1)(k+1)<2n+1(2k+1)n-k^2(k^2+1)+(2k+1)(k+1)<2n+1 or (2k+1)nk2(k2+1)+(2k+1)(k+1)>2n+4k+2(2k+1)n-k^2(k^2+1)+(2k+1)(k+1)>2n+4k+2 must be true.

Case 1: (2k+1)nk2(k2+1)+(2k+1)(k+1)<2n+1(2k+1)n-k^2(k^2+1)+(2k+1)(k+1)<2n+1

This can be reduced to 0>k(2nk3+k+3)0>k(2n-k^3+k+3) or 2n<k3k32n<k^3-k-3.

Case 2: (2k+1)nk2(k2+1)+(2k+1)(k+1)>2n+4k+2(2k+1)n-k^2(k^2+1)+(2k+1)(k+1)>2n+4k+2

This can be reduced to k(2nk3+k1)>1k(2n-k^3+k-1)>1 or 2n>k3k+1+1k2n>k^3-k+1+\frac { 1 }{ k }.

So the values that can be considered "eligible" (I don't even know what word to use right now, sorry) are k3k32nk3k+1+1kk^3-k-3\le2n\le k^3-k+1+\frac { 1 }{ k }.

Note that k3kk^3-k is divisible by 2 and 1k\frac{1}{k} is not an integer, so we can say that k3k22nk3k2\frac{k^3-k-2}{2} \le n \le \frac{k^3-k}{2}.

And as a result, the two chains of 2k+22k+2 numbers that we are looking for are k3k22,k3k2,...,k3+3k2\frac { k^3-k-2 }{ 2 } ,\frac { k^3-k }{ 2 } ,...,\frac { k^3+3k }{ 2 } and k3k2,k3k+22,...,k3+3k+22\frac { k^3-k }{ 2 } ,\frac { k^3-k+2 }{ 2 } ,...,\frac { k^3+3k+2 }{ 2 } .

For k=3k=3, the two chains that we are looking for are 11,12,13,14,15,16,17,1811, 12, 13, 14, 15, 16, 17, 18 and 12,13,14,15,16,17,18,19 12, 13, 14, 15, 16, 17, 18,19.

Steven Jim - 3 years, 6 months ago

Log in to reply

@Jason Dyer Can you help me check this out? I may have made several mistakes here and there, or maybe this whole generalization is false.

Steven Jim - 3 years, 6 months ago

Log in to reply

Could we perhaps turn the answer into a question, and that way we can put yours (and Mike's) answers in? I think that will be a lot easier to inspect. (I would make the question something like: on an antimagic square [insert definition], how many of these might be the start of the sequence of consecutive sums? List 8, 9, 12, 13, and have the options All 4, Only 3, Only 2, Only 1, None of Them where None of them is the correct choice.)

Jason Dyer Staff - 3 years, 6 months ago

Log in to reply

@Jason Dyer Hmm... Shall I also make a generalisation for all n? :)

Okay, I’ll try and make a good question before posting it.

And (stupid question) who is gonna post this?

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim Whoever gets there first, I suppose? If there isn't a related question in the group yet and you're ready, go ahead and post it.

Jason Dyer Staff - 3 years, 6 months ago

Log in to reply

@Jason Dyer Okay... What about the generalization? You think it will work?

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim I have had time enough to crunch it on a little; I'm fairly sure it's fine.

Jason Dyer Staff - 3 years, 6 months ago

Log in to reply

@Jason Dyer I just have a feeling I can only post a yes/no question, mainly because people know a 3x3 does not exist. I'm stuck posting this one :/

Steven Jim - 3 years, 6 months ago

I started looking for a reason no 3x3 antimagic square exists. To be more specific, I started looking at the relations between even and odd numbers. We need to place the numbers 1 through 9. Of those numbers, 4 are even and 5 are odd. Furthermore, there are a total of 8 sums: 3 rows, 3 columns, and 2 diagonals. These sums must be consecutive numbers, so 4 of these sums are even and 4 are odd.

I started looking for all the ways of placing 4 even and 5 odd numbers in a 3x3 square and calculated how many of the 8 sums would evaluate to some even number. If exactly 4 of these sums were even, it's a valid way of placing even and odd numbers. I found that only 17 ways of ordering even and odd numbers were valid. After taking out rotations, only 5 ways were left. There are the 5 ways:

[000101111][001011110][001110110][010101101][101010101]\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix}\begin{bmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}

0 represents some even number and 1 represents some odd number. Source code I used for finding those orderings

I also did some math on how many ways there are to arrange the numbers 1 through 9. There are 9! = 362,880 ways. Furthermore, there are (94)=126\binom{9}{4} = 126 ways of placing 4 even numbers and 5 odd numbers, and 109 of those don't produce the required 4 even and 4 odd sums. So 362,880/126109=313,920362,880 / 126 * 109 = 313,920 of the orderings are impossible.

Stefan van der Waal - 3 years, 6 months ago

(LaTeXLaTeX is up, please let me know if there's still any errors.)

As usual, we label the squares as such:

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

Mike and Steven Jim have established that only two sequences are possible for a 3x3 anti-magic square: 11,12,,1811, 12, \dots, 18 and 12,13,,19.12, 13, \dots, 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},\{1, 2, \dots, 9\}, their sum is equal to 45, and the diagonal sum is

(a+e+i)+(c+e+g)=1162(45)=26. (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).(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. (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+4526=3e+19.(b + e + h) + (d + e + f) = 3e + 45 - 26 = 3e + 19.

There are only two pairs of distinct integers in the range [11,18][11, 18] that sum to 26: (11,15)(11, 15) and (12,14).(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+191 ⁣(mod3).3e + 19 \equiv 1 \! \pmod{3}. Here we must do some casework:

  • If we chose (11,15)(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).(12, 13), (12, 16), (13, 18), (14, 17), (16, 18).

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

For each possible middle sum pair, we can find the value of ee i.e. the middle number by using middle sum = 3e+19.3e + 19. For example, if we chose (11,15)(11, 15) for the diagonals and (14,17)(14, 17) for the middles, then e=14+17193=4.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 ee is between 2 and 5 inclusive.

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

Steven Yuan - 3 years, 6 months ago

Log in to reply

Eh, call me Steve.

There is a proof that the middle number must be odd, which I will add after my tests (which I haven’t revised, damn) So, for the sequence of numbers from 11 to 18, you have e equal to 3 or 5, and for the sequence from 12 to 19, you have e equal to 5 or 7. Yup.

Steven Jim - 3 years, 6 months ago

Log in to reply

In fact, with the cases I've described, we might be able to directly check if they're possible or not by using the value for ee to find a+i,c+g,b+h,d+f,a + i, c + g, b + h, d + f, then finding both (a+b+c)+(g+h+i)(a + b + c) + (g + h + i) (outer rows) and (a+d+g)+(c+f+i)(a + d + g) + (c + f + i) (outer columns) and seeing if we can still assign the remaining sum values to those rows and columns. It's a little brute force, but at least we only need to check 10 or so cases rather than 300,000+.

And thanks for the correction, Steve ;-) (it's a little awkward having two people with the same first name together)

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan I've made some calculations, and it seems like if we seperate the numbers like (a+i),(c+g)(a+i),(c+g) and (b+h),(d+f)(b+h),(d+f), we will only have 20 cases to consider. The bad thing here is if we try to find numbers from aa to ii seperately, we will have upto 320 cases, a lot of which we can immediately say as false but can't point out.

Maybe we do need some good Computer Science users to help here. The cases, I will type here later. @Steven Yuan You know anyone who is good at CS?

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim Actually, we might not need them. By using the outer row and outer column sum tests, I was able to reduce the number of cases from 20 to 12. If what you say is true, and the middle number must be odd, then we only have a grand total of 4 cases to check by hand. Just 4!!! (Although I haven't seen your justification for why the middle number must be odd yet, so I'm taking your word for it)

And also because I've got all the sums planned out for each case, we can plausibly use logical methods to take care of them. We might not need the computers :D

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Hmm... You've gotten a point. Never mind 'bout ee being odd. False calculation :) Sorry for not updating on that anyways, forgot :/

Why don't you update your comment? That way, I'd know 'bout how you reduced the 8 cases! Really, I'm excited!

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim OK, I'll make a separate update post in a bit. And too bad that it turned out to be false, it could've saved a lot of work!

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Oh, okay. Tag me in so that I could know, will ya? I'll be waiting :)

And yeah, pretty much a shame.

Steven Jim - 3 years, 6 months ago

@Steven Jim here it is. (Sorry it took so long, I hurt my hand recently so typing is much harder. Also, this post is a continuation of my first one.)

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

DiagonalsMiddlese(11,15)(12,13)2(12,16)3(13,18)4(14,17)4(16,18)5(12,14)(11,17)3(13,15)3(13,18)4(15,16)4(16,18)5(15,19)(12,14)5(12,17)6(13,16)6(14,18)7(17,18)8(16,18)(12,14)5(12,17)6(13,19)7(14,15)6(15,17)7 \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}

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

a+c+g+i=262e=262(4)=18, a + c + g + i = 26 - 2e = 26 - 2(4) = 18,

and we also have

b+h=13e=134=9d+f=18e=184=14. b + h = 13 - e = 13 - 4 = 9 \\ d + f = 18 - e = 18 - 4 = 14.

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

(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. \begin{aligned} (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{aligned}

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)(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)(11, 15) and (13,18),(13, 18), respectively.

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

DiagonalsMiddles(11,15)(12,16)(13,18)(12,14)(13,15)(16,18)(15,19)(12,17)(14,18)(16,18)(12,14)(15,17) \begin{array}{c|c} \text{Diagonals} & \text{Middles}\\ \hline (11, 15) & (12, 16) \\ & (13, 18) \\ \hline (12, 14) & (13, 15) \\ & (16, 18) \\ \hline (15, 19) & (12, 17)\\ & (14, 18) \\ \hline (16, 18) & (12, 14) \\ & (15, 17) \end{array}

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

EDIT: After reviewing the even-odd placements that Stefan provided us in a different comment, we were able to remove all of the (12,14)(12, 14) and (16,18)(16, 18) diagonal sum cases, leaving us with only 6 cases left to check:

DiagonalsMiddles(11,15)(12,13)(14,17)(16,18)(15,19)(12,14)(13,16)(17,18) \begin{array}{c|c} \text{Diagonals} & \text{Middles}\\ \hline (11, 15) & (12, 13) \\ & (14, 17) \\ & (16, 18) \\ \hline (15, 19) & (12, 14)\\ & (13, 16) \\ & (17, 18) \end{array}

Steven Yuan - 3 years, 6 months ago

Log in to reply

Oh... Gotcha. So we jump straight into the next 12, right?

Just posted a problem on the group. If you're free, help me out on checking it. Might make a stupid mistake here and there.

Steven Jim - 3 years, 6 months ago

Log in to reply

Sure, I'll take a look.

I was looking at Stefan's comment down below about possible placements of even and odd numbers, and I think we might be able to use it to remove even more cases. In particular, it seems like the diagonal sums must be odd no matter the parity of the middle number, which eliminates 6 more cases, so we're at 6 cases now!

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Yup. I'm looking into that too. Seems like you've gotten a point. What if the middle number is odd?

Oh yeah... How didn't I see that? Heck, 70% of the cases are already gone!

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim In fact, this could have discounted the (12, 14) and (16, 18) diagonal sums right from the beginning... if I had known about it. Well, we're already pretty close anyway, so it doesn't matter too much.

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Well... Jason said that we need to find an "as elegant as possible" solution, right? The shorter our solution is, the better it should be!

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim Yeah, I am a little wary of using computer algorithms though since the whole point is to avoid possible brute forcing. However, this is still a start.

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Well... Yeah. Is there a way to achieve Stefan's result without brute forcing?

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim I might take a look into that later, but for now I think I'll call it quits, I've been here for almost two hours now and need some rest. See ya!

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan See ya too, I've been here for 4 or 5 :) I sure do need a rest too :) Best luck on this one!

Steven Jim - 3 years, 6 months ago

@Steven Yuan Oh, and yeah, update the comment. Some are surely looking towards this (I hope) :)

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim Updated. And people will definitely be looking forward to this. :)

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Well... Have you thought one of writing the 6 cases down so that people would know? You don't have to, but it seems intimidating if you don't. Just an advice :)

Steven Jim - 3 years, 6 months ago

@Steven Yuan Good to hear the work I did was useful to you. Also, good job on the progress you guys have made so far. It looks like you're up to something.

Stefan van der Waal - 3 years, 6 months ago

Log in to reply

@Stefan van der Waal Well... 6 cases left. Of course (the other) Steve is up to finishing the proof.

Just a quick question here: Do you think you can prove your answer without brute forcing?

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim I'm currently searching for a proof that doesn't include brute forcing, and I think I'm up to something. Please give me some more time to figure it all out.

Stefan van der Waal - 3 years, 6 months ago

@Steven Jim You asked if I was able to proof it's impossible to have a 3x3 antimagic square where at least one diagonal is even. I think I've managed to do it.

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

[abcdefghi] \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}

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, 4 must be even and 4 odd

Since the combined sum of all rows, columns, and diagonals must be even, we can calculate the following: (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+3ia+c+g+i0 (mod 2)(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)

So a+c+g+i 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 3x3 matrix. 1 means 'some odd number' and 0 means 'some even number': [010111010] \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 3x3 matrix: [111000101] \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 3x3 matrix now looks like this: [0?1?0?1?0] \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: [001101110] \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 3x3 matrix now looks like this: [1?0?1?1?0] \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: [100111100][110110100][110010110][110011100] \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix} The first matrix only has 2 even diagonals. The other 3 matrix has 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 subcase 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 3x3 antimagic square with at least one even diagonal. \square

Stefan van der Waal - 3 years, 6 months ago

Log in to reply

Yeah, I've just tried proving. Mine looks kinda same to yours, it seems!

Steven Jim - 3 years, 6 months ago

@Steven Yuan Stefan got the proof! Any complaints about brute forcing now?

6 cases left anyways. Hand proof? Or elegance?

Steven Jim - 3 years, 6 months ago

Log in to reply

Looks good :thumbsup:

I was working on the casework, and it seems like we can eliminate two of the six possibilities with some logical deduction, but the other four might require a more drawn-out proof. I'll post details later.

Steven Yuan - 3 years, 6 months ago

Everyone is doing amazing at this! When we get a moment to breathe, could we put some of this on the wiki so we can organize the proof in sequence?

https://brilliant.org/wiki/open-problems-group-open-problem-2/

Jason Dyer Staff - 3 years, 6 months ago

Log in to reply

I don't know LaTeX, but I think that my bit should be first, then add on Steve's (Jim), followed by Steven's (Yuan). Then Stefen's work, followed by anything else I have forgotten. The reason for this is how the argument built up when we've been working.

Mike Harding - 3 years, 6 months ago

Log in to reply

@Mike Harding Feel free to post Latex-free - someone can always go in later and polish it up.

Jason Dyer Staff - 3 years, 6 months ago

I don't even know how to organize things on a wiki :/

Despite that, I think we should seperate the wiki into 2 parts: The work related to the 3x3 and the work related to your "general" question. That way, things should look better, and people won't misread.

Besides, don't let my proof in Mike's comment and my generalization to be on the same part. There's a reason I have to make a new comment for the generalization :)

Steven Jim - 3 years, 6 months ago

I just moved most of the work done here to the Wiki. If anybody has any comment, I'll hear it.

Stefan van der Waal - 3 years, 6 months ago

Log in to reply

@Stefan van der Waal For the third part, can you add the e values required in order for this to work? They're in the proof section below the statement.

Mike Harding - 3 years, 6 months ago

@Stefan van der Waal Thanks! Now everyone wins XD

Steven Jim - 3 years, 6 months ago

I've been thinking about the last 6 cases Steven Yuan presented.

DiagonalsMiddlese(11,15)(12,13)2(14,17)4(16,18)5(15,19)(12,14)5(13,16)6(17,18)8 \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}

So far the best approach to prove all of these cases don't result in 3x3 antimagic squares was to look at many different cases, but I think I've found a shorter proof.

Like usual, I use the following naming convention:

abcdefghi \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:

Diagonal 1: 9Diagonal 2: 13Middle 1: 10Middle 2:11(1,8)(4,9)(1,9)(3,8)(3,6)(5,8)(3,7)(4,7)(4,5)(6,7)(4,6)(5,6) \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:

Diagonal 1: 9Diagonal 2: 13Middle 1: 10Middle 2:11(1,8)(4,9)(3,7)(5,6)(3,6)(5,8)(1,9)(4,7)(4,5)(6,7)(1,9)(3,8) \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)(a + b + c), (g+h+i)(g + h + i), (a+d+g)(a + d + g), and (c+f+i)(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)(4 + 7 + 3 = 14), but it's impossible to create a 16 with the third option. Therefore the first case, (11,15)(11, 15) for the diagonals and (12,13)(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:

Diagonal 1: 7Diagonal 2: 11Middle 1: 10Middle 2:13(1,6)(2,9)(1,9)(5,8)(2,5)(3,8)(2,8)(6,7)(5,6)(3,7) \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 that case won't work:

Diagonal 1: 9Diagonal 2: 13Middle 1: 10Middle 2:11Reason it won’t work(2,5)(3,8)(1,9)(6,7)Impossible to make 13(1,6)(2,9)(3,7)(5,8)Impossible to make 12 \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. In this case, there's only one way of selecting the digits:

Diagonal 1: 6Diagonal 2: 10Middle 1: 11Middle 2:13(2,4)(1,9)(3,8)(6,7) \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.

12=4+1+713=4+1+8 12 = 4 + 1 + 7 \\ 13 = 4 + 1 + 8

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. In this case, there's only one way of selecting the digits:

Diagonal 1: 10Diagonal 2: 14Middle 1: 7Middle 2:9(1,9)(6,8)(3,4)(2,7) \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.

13=1+8+416=1+8+7 13 = 1 + 8 + 4 \\ 16 = 1 + 8 + 7

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:

Diagonal 1: 9Diagonal 2: 13Middle 1: 7Middle 2:10Reason it won’t work(2,7)(5,8)(3,4)(1,9)Impossible to make 12(1,8)(4,9)(2,5)(3,7)Impossible to make 18 \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:

Diagonal 1: 7Diagonal 2: 11Middle 1: 9Middle 2:10Reason it won’t work(1,6)(2,9)(4,5)(3,7)Impossible to make 16(2,5)(4,7)(3,6)(1,9)Impossible to make 14(3,4)(5,6)(2,7)(1,9)Impossible to make 13 \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, therefore there is no 3 by 3 antimagic square. \square

Stefan van der Waal - 3 years, 5 months ago

Log in to reply

Nice!

(General incidental comment - by Wednesday I am going to make an Update #1 post where I am going to try to summarize where the proof is and where the gaps are, to enough an extent that someone can jump in who just started without too much trouble.)

Jason Dyer Staff - 3 years, 5 months ago

Log in to reply

How extensive?

Besides, the proof is technically done :) You should type that in the update post :)

Steven Jim - 3 years, 5 months ago

Log in to reply

@Steven Jim Yeah, we just have to figure out for which n anti-magic squares exist. We know there are anti-magic squares for 4,5,6,8. We aren't sure about 7 yet, correct?

Mike Harding - 3 years, 5 months ago

Log in to reply

@Mike Harding I checked the previous research again, and that research found a way of generating a 7x7 antimagic square. http://ion.uwinnipeg.ca/~vlinek/jcormie/construct.html

I followed the instructions, and made this 7x7 antimagic square:

32414841119254047510202433466921233439781522353845141628293744117273036432132631424931218 \begin{array}{c|c|c|c|c|c|c} \hline 32 & 41 & 48 & 4 & 11 & 19 & 25 \\ \hline 40 & 47 & 5 & 10 & 20 & 24 & 33 \\ \hline 46 & 6 & 9 & 21 & 23 & 34 & 39 \\ \hline 7 & 8 & 15 & 22 & 35 & 38 & 45 \\ \hline 14 & 16 & 28 & 29 & 37 & 44 & 1 \\ \hline 17 & 27 & 30 & 36 & 43 & 2 & 13 \\ \hline 26 & 31 & 42 & 49 & 3 & 12 & 18 \\ \hline \end{array}

It also seemed like that source I just linked draws out a way of making an anti-magic square of any size >= 4. So it seems to me like the question of if antimagic squares of size 4x4 or larger exist isn't that open anymore.

Stefan van der Waal - 3 years, 5 months ago

Log in to reply

@Stefan van der Waal I have read inconsistent sources on the higher-level squares - I'm not sure what's going on there, but I wouldn't worry about that part. Let's just make sure the arguments in the 3x3 are as tight as they can be (quite often, after you finish a long proof, you find simplifications to the argument).

Jason Dyer Staff - 3 years, 5 months ago

@Stefan van der Waal Is that anti-magic square anti-magical, or fake?

Steven Jim - 3 years, 5 months ago

Log in to reply

@Steven Jim That 7x7 is anti-magical. Just checked.

Mike Harding - 3 years, 5 months ago

Log in to reply

@Mike Harding Crap. Seems like the answer for the generalised question is yes.

Steven Jim - 3 years, 5 months ago

@Stefan van der Waal Can we prove in any way that the methodology described always creates an anti-magic square?

Mike Harding - 3 years, 5 months ago

Log in to reply

@Mike Harding I just read a bit about the methodologies, and it seems to me like the methodology always creates an anti-magic square.

Stefan van der Waal - 3 years, 5 months ago

@Stefan van der Waal There's still another question that can be brought up: how many anti-magical squares of a certain size are there? This could be an interesting route now that we've pretty much nailed the 3x3 cases. Though I don't know if there's a way to find a formula without at least some computing power.

Steven Yuan - 3 years, 5 months ago

Log in to reply

@Steven Yuan Seems like there are only 2 of each. I’d like to invest in CS for a bit to make sure. If we know the answer, it should be easier to prove. Great question anyways!

@Jason Dyer Assume that the generalised question you given has been answered in the link Stefan gave earlier, you think we should invest on this question? It is potential, to me. (Sorry about the tag earlier)

Steven Jim - 3 years, 5 months ago

@Steven Yuan The website I linked to also has a section that addresses that question briefly. There seem to be 9,590,720 4x4 anti-magic squares and it isn't known how many 5x5 anti-magic squares there are. But since there are so many 4x4 anti-magic squares, I think it's safe to say the amount of anti-magic squares of larger sizes is huge.

Source: http://ion.uwinnipeg.ca/~vlinek/jcormie/enum.html

Stefan van der Waal - 3 years, 5 months ago

@Steven Jim Wait, that comment didn't previously have all 6 cases, right?

I need to do a very thorough check for correctness, and then I'm going to work on porting it to a single LaTeX file for publication. (Seriously!) I will discuss this more starting in January.

Jason Dyer Staff - 3 years, 5 months ago

Log in to reply

@Jason Dyer It didn’t. I checked though, looks like he’s right. Anyways, check out the wiki.

Woah. Publication? Seriously? Well then... You might wanna make a through check. I’m gonna check if we can simplify anything.

Steven Jim - 3 years, 5 months ago

Log in to reply

@Steven Jim We can definitely eliminate the (12, 14) and (16, 18) diagonal sum cases from my part because of Stefan's proof, so there's a major simplification we can do. Besides that, there isn't much else I think we can change, unless someone has an insight and manages to condense our work.

Steven Yuan - 3 years, 5 months ago

Log in to reply

@Steven Yuan Yeah, and apart from that, I think that I can re-type the first part of the proof so that it’s a lot shorter. However, I like Mike’s work. His proof of the center number smaller than the four other ones were fascinating, and he’s got credit on that (actually, he inspired me to the generalisation) Yeah, I’m pretty reluctant ‘bout that now.

Excluding that and everything seems as short as they can be. I guess we did well this week, but I still hope for some more eliminations. Maybe we all deserve a “Congrats!” :)

Right now, I’ll wait for Jason’s repost. Then, we might jump into your question. And to be honest, it seems interesting ;)

Steven Jim - 3 years, 5 months ago

@Jason Dyer Correct, I first wrote only the first two cases, and then posted it already, because I wanted to check if the LaTeX worked correctly (comments con't have preview buttons).

Stefan van der Waal - 3 years, 5 months ago

I have posted the update with the link to the proof.

Jason Dyer Staff - 3 years, 5 months ago

Brute force, still. I’ve to admit though that it’s really shorter. I’m waiting!

@Steven Yuan Check this out!

Steven Jim - 3 years, 5 months ago

Log in to reply

@Stefan van der Waal that looks pretty good! It's pretty much what I expected the proof to end up at, but perhaps someone else could find a more condensed or elegant method.

Steven Yuan - 3 years, 5 months ago

I did some googling, and found a few links to work done by other people, so we already have a start:

Stefan van der Waal - 3 years, 6 months ago

Log in to reply

So for all even nn, the answer is yes, right? Well... Maybe none exists for odd ones. What do you think?

Steven Jim - 3 years, 6 months ago

Log in to reply

They exist for odd ones. Wikipedia has two examples of anti-magic squares that are 5x5. https://en.wikipedia.org/wiki/Antimagic_square Also, there is no anti-magic square of 2x2.

Stefan van der Waal - 3 years, 6 months ago

Log in to reply

@Stefan van der Waal Of course none exists for 2x2. So... Do there exist 1 for 7x7?

Steven Jim - 3 years, 6 months ago

@Stefan van der Waal Wait... there's an error in the Wikipedia article! The leftmost 5x5 anti-magic square they give includes two 16s, which is not valid. The top left 16 needs to be replaced by a 5.

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan Well... What can we say? Wikipedia isn't correct!

Yeah, seen that too. Anyways, it writes "In the antimagic square of order 5 on the left, the rows, columns and diagonals sum up to numbers between 60 and 71. In the antimagic square on the right, the rows, columns and diagonals add up to numbers between 59 and 70", which are the exact sequence I've proved generally! Phew, now I can say my proof is true XD

Steven Jim - 3 years, 6 months ago

Log in to reply

@Steven Jim Hence wikipedia is never a source for anything. Also change it if it needs changing.

Mike Harding - 3 years, 6 months ago

@Steven Yuan I just fixed that error on Wikipedia.

Stefan van der Waal - 3 years, 6 months ago

We know that the AMS must have the integers from 1-9. Let us formalize this as follows. A1,A2,A3 B1,B2,B3 C1,C2,C3 A2,B1,C2,B3 are edges A1,A3,C1,C3 are corners, B2 is the center.

A1+B1+C1=R1 A2+B2+C2=R2 A3+B3+C3=R3 A1+A2+A3=A B1+B2+B3=B C1+C2+C3=C A1+B2+C3=X C1+B2+A3=Y R1+R2+R3=A+B+C=45 A1 through C3 are distinct integers from 1-9. R1+R2+R3+A+B+C+X+Y=(N+1)N/2-(M-1)M/2, where M is the lowest sum and N is the highest sum. Notice that N=M+7. 45+45+A1+C1+A3+C3+2B2=(M+8)(M+7)/2-(M-1)M/2=(M^2+15M+56-M^2+M)/2=(16M+56)/2=8M+28 62+A1+C1+A3+C3+2B2=8M This tells us that A1+C1+A3+C3 is even, meaning the corners must have 0, 2, or 4 odd numbers. If A1=2,C1=3,A3=4,C3=5,B2=1, then the lowest possible value of M is ceil((62+2+3+4+5+2)/8)=10. If B2=9,A1=8,A3=7,C1=6,C3=5, then the highest possible value of M is floor((62+18+8+7+6+5)/8)=13.

This means the lowest of the sums must be either 10,11,12, or 13, and the highest of the sums must be either 17,18,19,20.

Let's look at the center. We see that it creates four pairs of numbers whose sums (R2,B,X,Y) must be distinct, such that 20>=S_n>= 10. This means the minimum sum of the pair sums is 10+11+12+13=50. This means that A1+B1+C1+C2+C3+B3+A3+A2+4B2>=50, or 45+3B2>=50, or 3B2>=5, or B2>=2, meaning B2 cannot be 1.

Marcus Luebke - 3 years, 6 months ago

Log in to reply

I'm sure 10+11+12+13 doesn't equal 50. Great job though.

Steven Jim - 3 years, 6 months ago

I apologize for the error (I think it's funny). Also, I've noticed that people are using "a" through "i", so in future work I will use that. I'll also commit to using LaTeXLaTeX in the future, so it's mostly readable.

Marcus Luebke - 3 years, 6 months ago

Okay. I've just had an idea on proving if n2n^2 anti-magic squares do exist for n4n \ge 4. So for all even nn, Stefan Van der Waal found out a link which shows us the proof. For odd nn, if we can show that a 727^2 anti-magic square does exist, we may prove that 33 is the maximum value so that no anti-magic square exists. However, if we can prove that a 727^2 anti-magic square does not exist, we can prove that the general question is only true when n=4k+1n=4k+1, with k1k\ge1. What are your thoughts?

Steven Jim - 3 years, 6 months ago

I just had a thought, don't know how useful it might be but it could make an interesting problem here on Brilliant. This concerns the possible diagonal sums in a k×kk \times k anti-magic square, where kk is an odd number greater than 3, and it is an extension of the work done for the 3x3 case.

We've established that for any k,k, there are only two possible sum sequences for the k×kk \times k anti-magic square: k3k22,k3k2,,k3+3k2\frac{k^3 - k - 2}{2}, \frac{k^3 - k}{2}, \dots, \frac{k^3 + 3k}{2} and k3k2,k3k+22,,k3+3k+22.\frac{k^3 - k}{2}, \frac{k^3 - k + 2}{2}, \dots, \frac{k^3 + 3k + 2}{2}. Let's focus on the first sequence. The sum of the numbers in this sequence is

12(2k+2)(k3k22+k3+3k2)=(k+1)(k3+k1)=k4+k3+k21. \dfrac{1}{2}(2k + 2) \left ( \dfrac{k^3 - k - 2}{2} + \dfrac{k^3 + 3k}{2} \right ) = (k + 1)(k^3 + k - 1) = k^4 + k^3 + k^2 - 1.

The sum of all the integers from 1 to k2k^2 inclusive is simply k4+k22.\frac{k^4 + k^2}{2}. This is equal to both the sum of all the rows equals the sum of all the columns in the square, since both cases cover all the integers on the grid. Let d1,d2d_1, d_2 be the diagonal sums, with d1<d2.d_1 < d_2. We can write

Sum of sequence=Rows+Columns+Diagonalsk4+k3+k21=2(k4+k22)+d1+d2k4+k3+k21=k4+k2+d1+d2d1+d2=k31. \begin{aligned} \text{Sum of sequence} &= \text{Rows} + \text{Columns} + \text{Diagonals} \\ k^4 + k^3 + k^2 - 1 &= 2 \left ( \dfrac{k^4 + k^2}{2} \right ) + d_1 + d_2 \\ k^4 + k^3 + k^2 - 1 &= k^4 + k^2 + d_1 + d_2 \\ d_1 + d_2 &= k^3 - 1. \\ \end{aligned}

Since kk is odd, k31k^3 - 1 is even, and k312\frac{k^3 - 1}{2} is an integer. Clearly, k312<k3+3k2,\frac{k^3 - 1}{2} < \frac{k^3 + 3k}{2}, and we also have k312>k3k22,\frac{k^3 - 1}{2} > \frac{k^3 - k - 2}{2}, as that reduces to k>1.k > -1. Thus, k312\frac{k^3 - 1}{2} is part of the sequence of sums.

Finally, the number of possible values of d1,d_1, which is also equal to the number of pairs (d1,d2),(d_1, d_2), is just k312k3k22=k+12,\frac{k^3 - 1}{2} - \frac{k^3 - k - 2}{2} = \frac{k + 1}{2}, since we must exclude k312\frac{k^3 - 1}{2} as it will cause d1=d2,d_1 = d_2, and any other value less than that is permissible. Therefore, there are k+12\frac{k + 1}{2} possible diagonal sum pairs for the first sequence of sums.

Applying the same logic to the second sequence, which starts at k3k2,\frac{k^3 - k}{2}, we find another k+12\frac{k + 1}{2} diagonal sum pairs. The total number of possible diagonal sum pairs is k+1.k + 1.

Steven Yuan - 3 years, 6 months ago

Log in to reply

Oh yeah... Whatever we do, d1+d2d_1+d_2 is always equal to a constant! Hell...

Steven Jim - 3 years, 6 months ago

Log in to reply

Well, it can take on two possible values based on the sequence we choose, but once we choose one it must stay that way, so yeah pretty much.

I just posted a problem for my New Year's Countdown series related to this result. Can you check to see if it's OK?

Steven Yuan - 3 years, 6 months ago

Log in to reply

@Steven Yuan 3+5+7=15, not 19

Mike Harding - 3 years, 6 months ago

Log in to reply

@Mike Harding Oops, thanks for pointing that out! It's now fixed

Steven Yuan - 3 years, 6 months ago

Okay... @Steven Yuan @Stefan van der Waal @Mike Harding I've been trying to do some brute force with the remaining 6 cases, but I just found out that there are too many sub-cases to consider.

First of all, yes, I can find the values from aa to ii. The problem is: For every pair of diagonal and middle sums, there seem to be at least 4 sub-cases. Also, there are 8 ways to rearrange (without rotation, hell) the 3x3 board so that the diagonal and middle sums remain the same, yet the other sums. So... Yes... We will have at least 192 sub-cases to consider. That's not how I want to finish the proof, tbh. So... We do need a way to throw more cases away. Ideas?

Steven Jim - 3 years, 6 months ago

Log in to reply

Well, it is possible to eliminate at least two of them just by logical deduction. They are D:(11,15),M:(16,18)D: (11, 15), M: (16, 18) and D:(15,19),M:(12,14).D: (15, 19), M: (12, 14). As for the rest, we definitely need something better

Steven Yuan - 3 years, 6 months ago

Log in to reply

Okay... We still have 100+ sub-cases... The elimination seems plausible, but I'd like to see your proof. Would that be possible?

Steven Jim - 3 years, 6 months ago

There are 3120 unique 3x3 heterosquares.

Marcus Luebke - 3 years, 6 months ago

Log in to reply

Brute force, by hand? Nah...

Steven Jim - 3 years, 6 months ago

Log in to reply

The objective is to find a way to prove it other than brute force.

Mike Harding - 3 years, 6 months ago

They asked us not to do brute force for AMS. They didn't say no brute force for heterosquares. Also, computers are much faster than by hand...

Marcus Luebke - 3 years, 6 months ago
×

Problem Loading...

Note Loading...

Set Loading...