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 by antimagic squares exist for all 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.
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\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.
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.
Amazing! Anyways, isn't it 8≤n≤13?
Also, if you add the sum of the diagonals, you fill find out that 8n+28≥106, which means n≥10. First two chains gone, right?
Also note that if a+c+2e+g+i≤20, either a+e+i≤9 or g+c+e≤9 is true (first two chains gone, which makes this an impossibility), which means T≥111 or n≥11. 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 132−90=42>20+19. Two to go. (Marcus' idea can be taken, although 10+11+12+13=46. At least 11+12+13+14=50. Also, e must be odd and e can't be 9.)
Log in to reply
Trying to compile into wiki page. Why can't e be even?
Log in to reply
e can be either even or odd
Actually that was a mistake. I asked the other Steve, and he said his “proof” was invalid. SoI'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 n, to reduce "the chain of numbers that we need to worry about" to 2.
(Details of detailed proof when k=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 k2 square, there must be 2k+2 consecutive values for the k2 square to be anti-magic. Let n be the smallest value, then the 2k+2 consecutive values are n,n+1,...,n+2k+1, and the sum of those consecutive values are 2kn+2n+(2k+1)(k+1). The sum of the k2 numbers inside is 2k2(k2+1). Also, for a chain to be proved as incorrect, either (2k+1)n−k2(k2+1)+(2k+1)(k+1)<2n+1 or (2k+1)n−k2(k2+1)+(2k+1)(k+1)>2n+4k+2 must be true.
Case 1: (2k+1)n−k2(k2+1)+(2k+1)(k+1)<2n+1
This can be reduced to 0>k(2n−k3+k+3) or 2n<k3−k−3.
Case 2: (2k+1)n−k2(k2+1)+(2k+1)(k+1)>2n+4k+2
This can be reduced to k(2n−k3+k−1)>1 or 2n>k3−k+1+k1.
So the values that can be considered "eligible" (I don't even know what word to use right now, sorry) are k3−k−3≤2n≤k3−k+1+k1.
Note that k3−k is divisible by 2 and k1 is not an integer, so we can say that 2k3−k−2≤n≤2k3−k.
And as a result, the two chains of 2k+2 numbers that we are looking for are 2k3−k−2,2k3−k,...,2k3+3k and 2k3−k,2k3−k+2,...,2k3+3k+2.
For k=3, the two chains that we are looking for are 11,12,13,14,15,16,17,18 and 12,13,14,15,16,17,18,19.
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.
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.)
Log in to reply
Okay, I’ll try and make a good question before posting it.
And (stupid question) who is gonna post this?
Log in to reply
Log in to reply
Log in to reply
Log in to reply
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:
⎣⎡011001011⎦⎤⎣⎡001011110⎦⎤⎣⎡011011100⎦⎤⎣⎡011100011⎦⎤⎣⎡101010101⎦⎤
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 (49)=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/126∗109=313,920 of the orderings are impossible.
(LaTeX is up, please let me know if there's still any errors.)
As usual, we label the squares as such:
adgbehcfi
Mike and Steven Jim have established that only two sequences are possible for a 3x3 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≡1(mod3). 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 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=314+17−19=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∈[5,8] in this case. The middle number cannot be 1 or 9.
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.
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 e to find a+i,c+g,b+h,d+f, then finding both (a+b+c)+(g+h+i) (outer rows) and (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)
Log in to reply
(a+i),(c+g) and (b+h),(d+f), we will only have 20 cases to consider. The bad thing here is if we try to find numbers from a to i seperately, we will have upto 320 cases, a lot of which we can immediately say as false but can't point out.
I've made some calculations, and it seems like if we seperate the numbers likeMaybe 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?
Log in to reply
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
Log in to reply
e being odd. False calculation :) Sorry for not updating on that anyways, forgot :/
Hmm... You've gotten a point. Never mind 'boutWhy don't you update your comment? That way, I'd know 'bout how you reduced the 8 cases! Really, I'm excited!
Log in to reply
Log in to reply
And yeah, pretty much a shame.
@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, are shown here:
Diagonals(11,15)(12,14)(15,19)(16,18)Middles(12,13)(12,16)(13,18)(14,17)(16,18)(11,17)(13,15)(13,18)(15,16)(16,18)(12,14)(12,17)(13,16)(14,18)(17,18)(12,14)(12,17)(13,19)(14,15)(15,17)e23445334455667856767
For each 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
b+h=13−e=13−4=9d+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), and the sum of the "outer columns," (a+d+g)+(c+f+i).
(a+b+c)+(g+h+i)(a+d+g)+(c+f+i)=(a+c+g+i)+(b+h)=18+9=27=(a+c+g+i)+(d+f)=18+14=32.
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 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:
Diagonals(11,15)(12,14)(15,19)(16,18)Middles(12,16)(13,18)(13,15)(16,18)(12,17)(14,18)(12,14)(15,17)
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) and (16,18) diagonal sum cases, leaving us with only 6 cases left to check:
Diagonals(11,15)(15,19)Middles(12,13)(14,17)(16,18)(12,14)(13,16)(17,18)
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.
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!
Log in to reply
Oh yeah... How didn't I see that? Heck, 70% of the cases are already gone!
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Just a quick question here: Do you think you can prove your answer without brute forcing?
Log in to reply
@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:
⎣⎡adgbehcfi⎦⎤
From previous work we know the following:
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+3i≡a+c+g+i≡0 (mod 2)
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 3x3 matrix. 1 means 'some odd number' and 0 means 'some even number': ⎣⎡010111010⎦⎤ 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: ⎣⎡101100101⎦⎤
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⎦⎤ 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: ⎣⎡011001110⎦⎤ 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?1?1?0?0⎦⎤ There are 4 ways of placing the remaining 2 even and 2 odd numbers, after taking out reflections: ⎣⎡111010010⎦⎤⎣⎡111110000⎦⎤⎣⎡101111000⎦⎤⎣⎡101110010⎦⎤ 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. □
Log in to reply
Yeah, I've just tried proving. Mine looks kinda same to yours, it seems!
@Steven Yuan Stefan got the proof! Any complaints about brute forcing now?
6 cases left anyways. Hand proof? Or elegance?
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.
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/
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.
Log in to reply
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 :)
I just moved most of the work done here to the Wiki. If anybody has any comment, I'll hear it.
Log in to reply
I've been thinking about the last 6 cases Steven Yuan presented.
Diagonals(11,15)(15,19)Middles(12,13)(14,17)(16,18)(12,14)(13,16)(17,18)e245568
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:
adgbehcfi
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: 9(1,8)(3,6)(4,5)Diagonal 2: 13(4,9)(5,8)(6,7)Middle 1: 10(1,9)(3,7)(4,6)Middle 2:11(3,8)(4,7)(5,6)
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: 9(1,8)(3,6)(4,5)Diagonal 2: 13(4,9)(5,8)(6,7)Middle 1: 10(3,7)(1,9)(1,9)Middle 2:11(5,6)(4,7)(3,8)
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:
Diagonal 1: 7(1,6)(2,5)Diagonal 2: 11(2,9)(3,8)(5,6)Middle 1: 10(1,9)(2,8)(3,7)Middle 2:13(5,8)(6,7)
The two ways to select one from each column, together with the reason why that case won't work:
Diagonal 1: 9(2,5)(1,6)Diagonal 2: 13(3,8)(2,9)Middle 1: 10(1,9)(3,7)Middle 2:11(6,7)(5,8)Reason it won’t workImpossible to make 13Impossible to make 12
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: 6(2,4)Diagonal 2: 10(1,9)Middle 1: 11(3,8)Middle 2:13(6,7)
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
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: 10(1,9)Diagonal 2: 14(6,8)Middle 1: 7(3,4)Middle 2:9(2,7)
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
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: 9(2,7)(1,8)Diagonal 2: 13(5,8)(4,9)Middle 1: 7(3,4)(2,5)Middle 2:10(1,9)(3,7)Reason it won’t workImpossible to make 12Impossible to make 18
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: 7(1,6)(2,5)(3,4)Diagonal 2: 11(2,9)(4,7)(5,6)Middle 1: 9(4,5)(3,6)(2,7)Middle 2:10(3,7)(1,9)(1,9)Reason it won’t workImpossible to make 16Impossible to make 14Impossible to make 13
All 6 cases are impossible, therefore there is no 3 by 3 antimagic square. □
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.)
Log in to reply
How extensive?
Besides, the proof is technically done :) You should type that in the update post :)
Log in to reply
Log in to reply
I followed the instructions, and made this 7x7 antimagic square:
32404671417264147681627314859152830424102122293649112023353743319243438442122533394511318
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.
Log in to reply
Log in to reply
Log in to reply
Log in to reply
Log in to reply
@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)
Source: http://ion.uwinnipeg.ca/~vlinek/jcormie/enum.html
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.
Log in to reply
Woah. Publication? Seriously? Well then... You might wanna make a through check. I’m gonna check if we can simplify anything.
Log in to reply
Log in to reply
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 ;)
I have posted the update with the link to the proof.
Brute force, still. I’ve to admit though that it’s really shorter. I’m waiting!
@Steven Yuan Check this out!
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.
I did some googling, and found a few links to work done by other people, so we already have a start:
Log in to reply
So for all even n, the answer is yes, right? Well... Maybe none exists for odd ones. What do you think?
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.
Log in to reply
Log in to reply
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
Log in to reply
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.
Log in to reply
I'm sure 10+11+12+13 doesn't equal 50. Great job though.
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 LaTeX in the future, so it's mostly readable.
Okay. I've just had an idea on proving if n2 anti-magic squares do exist for n≥4. So for all even n, Stefan Van der Waal found out a link which shows us the proof. For odd n, if we can show that a 72 anti-magic square does exist, we may prove that 3 is the maximum value so that no anti-magic square exists. However, if we can prove that a 72 anti-magic square does not exist, we can prove that the general question is only true when n=4k+1, with k≥1. What are your thoughts?
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×k anti-magic square, where k 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, there are only two possible sum sequences for the k×k anti-magic square: 2k3−k−2,2k3−k,…,2k3+3k and 2k3−k,2k3−k+2,…,2k3+3k+2. Let's focus on the first sequence. The sum of the numbers in this sequence is
21(2k+2)(2k3−k−2+2k3+3k)=(k+1)(k3+k−1)=k4+k3+k2−1.
The sum of all the integers from 1 to k2 inclusive is simply 2k4+k2. 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,d2 be the diagonal sums, with d1<d2. We can write
Sum of sequencek4+k3+k2−1k4+k3+k2−1d1+d2=Rows+Columns+Diagonals=2(2k4+k2)+d1+d2=k4+k2+d1+d2=k3−1.
Since k is odd, k3−1 is even, and 2k3−1 is an integer. Clearly, 2k3−1<2k3+3k, and we also have 2k3−1>2k3−k−2, as that reduces to k>−1. Thus, 2k3−1 is part of the sequence of sums.
Finally, the number of possible values of d1, which is also equal to the number of pairs (d1,d2), is just 2k3−1−2k3−k−2=2k+1, since we must exclude 2k3−1 as it will cause d1=d2, and any other value less than that is permissible. Therefore, there are 2k+1 possible diagonal sum pairs for the first sequence of sums.
Applying the same logic to the second sequence, which starts at 2k3−k, we find another 2k+1 diagonal sum pairs. The total number of possible diagonal sum pairs is k+1.
Log in to reply
Oh yeah... Whatever we do, d1+d2 is always equal to a constant! Hell...
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?
Log in to reply
Log in to reply
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 a to i. 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?
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) and D:(15,19),M:(12,14). As for the rest, we definitely need something better
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?
There are 3120 unique 3x3 heterosquares.
Log in to reply
Brute force, by hand? Nah...
Log in to reply
The objective is to find a way to prove it other than brute force.
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...