Can distinct integers with 8 subsets of 3 always form a magic square?

[Greg Bernhardt]

This challenge has been provided by @Joffan

A magic square has rows, columns and diagonals summing to the same number. For a 3x3 magic square there are 8 such sums.
Given a set of 9 distinct integers which has at least 8 subsets of 3 all with a common sum, is it always possible to make a magic square with those integers?

 

[jedishrfu]

There is only one solution for 3x3 magic square discounting rotations and reflections known as the Lo Shu square:

http://en.wikipedia.org/wiki/Lo_Shu_Square

 

[Joffan]

The 9 integers are not necessarily 1,2,3,4,5,6,7,8,9 - the challenge refers to an arbitrary set of integers with a certain property of some subsets.

 

[jedishrfu]

Are you saying Lo Shu is not unique in the 3x3 space? you're allowing for negative values? real number values? ...

 

[jedishrfu]

It seems that if you add the same delta value to each square then you can produce an infinite number of 3x3 squares. This would imply that the set of 9 numbers must be in consecutive order like 1-9 or 2-10 or 11-19...

 

[lpetrich]

Here goes. Let's consider all the possibilities. First, one could abstract from integers and addition to any commutative semigroup, with appropriate generalizations of subtraction, multiplication by an integer, and division by an integer.

Let's call the subset sum SSS. It will be shared by the 8 3-element subsets of the 9 numbers that we wish to find.

Each number has a subset membership count or SMC. The sum of all the SMC's = sum of all the subset sizes = 3*8 = 24Two of the subsets can either be disjoint or else share only one number. They cannot share two numbers, otherwise the third number of each would be the same, violating the problem conditions. Thus, a number with SMC = 2 is in 2 subsets that span 5 numbers. Likewise, SMC = 3 means spanning 7 numbers and SMC = 4 means spanning 9 numbers -- all of them. Thus, the maximum SMC is 4.

Let's see what happens when one number has SMC = 4. If that element with SMC = 4 is 1, then its subsets are
1 2 3, 1 4 5, 1 6 7, 1 8 9
where the numbers here are which ones of the original set's numbers. One can find the value of number 1, N(1). Add the number of the subsets together. One gets 3*N(1) + Total = 4*SSS. That means that there is at most one number with SMC = 4.

If there is such an number, then at least two of the problem's subsets are disjoint. The next subset has a number from 3 of that number's 4 subsets, thus it is disjoint with the 4th one.Let's now consider what would happen if the maximum SMC was 3. It cannot be less than that, because the average SMC is 2 2/3. With that maximum, the SMC values can be 6 3's and 3 2's, or 7 3's, and one each of 2 and 1.

For anyone of the numbers with SMC = 3, one can make the subsets
1 2 3, 1 4 5, 1 6 7
with extra numbers 8 9. A subset that involves them while keeping max SMC = 3 must have forms 2 4 8 or 2 8 9, thus being disjoint to 1 6 7. Thus in this case also, at least two of the subsets are disjoint.I have only a partial solution, but I will post it. I will continue in my next post here.

 

[lpetrich]

Since we have two disjoint subsets, our task is simplified. Can the remaining three numbers be in a third disjoint subset? If they aren't, then can the remaining subsets contain a set of three disjoint ones? Let's consider the second possibility. The remaining subsets contain one number from the first subset, one from the second subset, and one from the leftover numbers, or else one from the first two subsets and two from the leftover numbers. At most three of the subsets can be the latter type.

If no pairs in the leftover numbers, then if 1 has SMC = 4, then we can have, without loss of generality
1 2 3, 4 5 6, 1 4 7, 1 5 8, 1 6 9
Continuing, we select 2 4 8 and either 2 5 7, 2 5 9, or 2 6 7.

There is a problem with 2 4 8, 2 5 7. Consider it with 1 4 7 and 1 5 8. The sum of the first two is 2N(2) + N(4) + N(5) + N(7) + N(8). The sum of the second two is like this, but with N(1) instead of N(2). Thus, N(2) = N(1), which is invalid.

Then after that, subsets starting with 3. After some experimentation, I was able to find some disjoint-triplet subsets, but also some subset solutions that are not. So it's up in the air at this point.If there are three disjoint subsets, then we find 3*SSS = Total, and 3*N(SMC = 4) = SSS, or 9*N(SMC = 4) = Total. This makes N(SMC = 4) the average of all the numbers.

If there are three disjoint subsets, then we get even more simplification. The remaining five subsets have one from each of those subsets.

Here is a possible solution with three disjoint subsets but no numbers with SMC = 4:
1 2 3, 4 5 6, 1 4 7, 1 5 8, 2 5 9, 2 6 7, 3 6 8, 3 4 9
However, it has N(1) = N(6) = N(9), N(2) = N(4) = N(8), and N(3) = N(5) = N(7).

I may have to find some way of trial-and-error testing that does not take either complicated code design or excessive run time.Returning to the case of one number with SMC = 4, I will consider the remaining four subsets. I start with
1 2 3, 1 4 5, 1 6 7, 1 8 9
The additional subsets take at most one from each. We can start with 2 4 6. Since there is not enough room in 2 to 8 to have 4 additional subsets with SMC = 2 for those numbers, at least some of them must have SMC = 3. We can let 2 have SMC = 3. We get two possibilities:
1 2 3, 1 4 5, 1 6 7, 1 8 9, 2 4 6, 2 5 7
1 2 3, 1 4 5, 1 6 7, 1 8 9, 2 4 6, 2 5 8
Unfortunately, I get lots of possibilities for the remaining two subsets.

 

[lpetrich]

I've found several possible sets of subsets of the numbers that don't match a magic-square topology, like
{{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {1, 8, 9}, {2, 4, 6}, {2, 5, 8}, {3, 6, 8}, {4, 7, 9}}

It has solution
{1, 0, -1, 3, -4, -3, 2, 4, -5}
chosen to make all the subset sums zero. But its mean is 1/3, which is none of those numbers.

From my earlier discussion, the number with SMC = 4 is the mean of all of them if three of the subsets are disjoint. That condition is satisfied for a magic square, so if the mean of a set of numbers is not in that set, then that set cannot be a solution of a magic square.

So there are some sets of 9 numbers that have 8 3-element subsets of them with equal sums, but that cannot be magic-square solutions.

 

[Joffan]

Great work lpetrich!