Zack’s Mom Knows
A puzzle with a story
Dick Karp needs no introduction. So I will give him none. Okay I will say that it has been an honor to know him for many years—we met right after I graduated from CMU, a pleasure to work with him on a few projects, and always fun to see.
Today I wish to talk about a recent dinner conversation I had with Dick and Noga Alon.
The dinner was the Simons advisory committee dinner this last Friday. At some point we were talking about stories of our kids. I was sitting between Dick and Noga. I had just talked about my daughter Jen, when Dick told a story about a phone call he once made to his son, years ago.
Dick was on a trip for business and called home to say hi to his son, Jeremy. His son asked, after some chit-chat:
Dad, did you solve that problem about the hexagon yet?
Dick answered no, that he had not. Then Jeremy said,
Well Zack’s mom did.
Karp said that was it. Forget about the talk he had to give the next day, about other work, about research, he had to solve the puzzle. Note: I do not think it mattered that it was Zack’s Mom or Dad, just that it was solved by someone. As a father I can imagine, my reaction would have been the same. If Jen had said
The Puzzle
The problem is an innocent question about labeling a hexagon. The problem is to assign the integers 
Dick Solves The Problem
Dick said that he did find a solution that night. He told us that he first found an argument, which he could not recall, that the common value was 
Noga started to sketch on a napkin a hexagon and we tried to figure out what the common number had to be. I gave a trivial lower bound, but we could not see why it had to be 
which I believe is better. But Dick said that it could be done by hand. The dinner ended with me heading off to my hotel to get some rest. I do not know if Dick and Noga finished solving the problem once I left—I would not be surprised if they did.
The Solution
When I started to write this piece I thought that I should first get a solution to the problem. I could have tried to do it by hand, or written a program as Noga suggested, but I used another method: Google search.
The problem sounded to me related to another notorious open problem called the graceful graph conjecture—more on that in a bit. I was wrong about that connection, they do not seem to be related in any obvious way. However, the hexagon problem has been studied since at least 1970. The general problem is: Given an undirected graph 
so each number is used exactly once, and the edges have the same magic sum. Again the magic sum of an edge is the sum of the number assigned to the edge plus the values assigned to its endpoints. Such labeling are called edge-magic labelings.
See the paper by Andrew Baker and Joe Sawada for some nice results and further references. Or see the book Magic Graphs by Alison Marr and Walter Wallis.
Unlike the case of a magic square, the fact that vertex numbers are used a different number of times from edge numbers makes it possible to have solutions with different common magic-sum values.
Here is one solution; there are I believe at least three with different common sums. Click it to see the answer.
Note, the common value here is 
Open Problems
I believe that finding the number of edge-magic labelings is open: both in the sense of a fast algorithm and in the sense of an analytic solution. Even an asymptotic bound seems hard.
If you like interesting labeling problems there is another innocent sounding problem: Does every tree have a graceful labeling? This problem is notorious, is open now for about sixty years, and is only known for special types of trees and small ones, trees with at most 
[fixed typo]
Each number on a vertex contributes to two of the sums; each number on an edge contributes to one of the sums. So, if you take two times the sum of the vertex numbers, and add the edge numbers, you will get 6 times the magic sum. This is the same thing as summing all twelve numbers (getting 78), and adding the sum of the vertex numbers; you must get 6 times the magic sum when you do that. Since 78 is a multiple of 6, the sum of the vertex numbers must be a multiple of 6.
The smallest multiple of 6 you can get by adding six of the numbers is 24: 1+2+3+5+6+7 is one way. If the vertex numbers sum to 24, then the magic sum will be (78+24)/6=17. The largest multiple of 6 you can get by adding six of the numbers is 54: 6+7+8+10+11+12 is one way. If the vertex numbers sum to 54, then the magic sum will be (78+54)/6=22. So, the magic sum must be something from 17 to 22.
I can confirm that all six totals are possible. But I won’t spoil any more. 🙂
For any solution $x_1, \ldots,x_12$ with magic sum M, one can take the solution $13-x_1,\ldots,13-x_12$ which has magic sum 39-M. Since 39 is odd, this means that there cannot be only one possible magic sum.
I found one solution by trial-and-error. One idle observation is that the set of solutions over the field Z/13Z is permuted by simultaneously multiplying all the elements by the diagonal action of (Z/13Z)^*. There are “distinct” solutions (over Z) that are in the same orbit of this action (two of them below the fold), but for a “silly” reason. I wonder how many orbits there are of this action? What about if one also throws in the obvious dihedral group action?
(spoiler below)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
—————-
(spoiler: please feel free to delete)
Multiplication by 12 mod 13 (i.e. subtracting each number from 13) transforms solutions over Z to other solutions over Z. This is a bit silly. Are there other pairs of solutions over Z that differ by multiplication in a “nontrivial” way?
__5_2_12
_6______4
8________3
_10_____9
__1_11_7
__8_11_1
_7______9
5________10
_3______4
__12_2_6
Another solution for 20
Notation: (number(v1),number(e), number(v2))
(1,11,8),
(8,2,10),
(10,4,6),
(6,9,5),
(5,3,12),
(12,7,1)
A toy/puzzle related to this is icosoku http://en.wikipedia.org/wiki/Icosoku and http://www.amazon.com/Recent-Toys-IC2869-IcoSoKu/dp/B003AIKTPU
The advertiser of Icosoku says that there is always a solution for every possible configuration of the pegs. I believe this based on my experience with this puzzle, but is there a mathematical proof?
After writing the six magic sum equations, it is easy to see that the sum of odd-numbered vertices is in [21,78]. This helps to show that the magic sum can range from 17 to 26. Even in an exhaustive search based program, these equations and the magic sum interval can then be used to prune the search space significantly.
My quick and dirty python script shows that there are 240 different solutions with magic sums ranging from 17 to 22. The number of solutions for each magic sum is as follows:
36 17
12 18
72 19
72 20
12 21
36 22
An example solution with the magic sum of 17 and its proof is:
sum: 17 vertices and edges in order a1-a12: 1 10 6 4 7 8 2 12 3 9 5 11
check 17 =a1+a2+a3=sum= 17
check 17 =a3+a4+a5=sum= 17
check 17 =a5+a6+a7=sum= 17
check 17 =a7+a8+a9=sum= 17
check 17 =a9+a10+a11=sum= 17
check 17 =a11+a12+a1=sum= 17
An example solution with the magic sum of 22 and its proof is:
sum: 22 vertices and edges in order a1-a12: 12 6 4 7 11 1 10 3 9 5 8 2
check 22 =a1+a2+a3=sum= 22
check 22 =a3+a4+a5=sum= 22
check 22 =a5+a6+a7=sum= 22
check 22 =a7+a8+a9=sum= 22
check 22 =a9+a10+a11=sum= 22
check 22 =a11+a12+a1=sum= 22
In the a1-a12 representation, the odd indexes are for the vertices and the even indexes are for the edges.
BTW, I did not remove solutions that are probably shifted versions of each other (due to the hexagon being a loop). My script assumes the vertex a1 is fixed. I will probably find time later to change my script to count unique solutions.
It is also possible to generalize this problem to any n-gon for n greater than 2.
It seems the sequence for the number of solutions for each n greater than 3 is recorded as A145692 or “Number of unique vertex-magic total labelings on cycle C_n” in Oct 16, 2008 in the The On-Line Encyclopedia of Integer Sequences.
And a practical application is?
Qasim
One of refs claims network application for labels, but unclear to me
I do respect knowledge given in solving this puzzle a lot. As a teacher of algorithms, number theory as related to cryptology, information theory to CS undergraduates, it is a constant struggle to maintain their attention in class. Students have constant access to social networks through their laptops and notebooks. In such situations real practical applications help a lot. A perfect example is explanation of negative weights on edges given by Prof. Sedgwick in his algorithm analysis II course from coursera. He connects negative cycles to arbitrage of currencies beautifully.
I face a similar problem teaching chinese remainder theorem. It is fascinating to be able to count the size of your army within an integer multiple, but is not very attractive to a lot of students. I have searched google for practical uses of this theorem but have not had much luck. Any references will be much appreciated.
Practical use of CRT? There are many I think that you could use.
1. How about RSA. The fast way to compute it is using CRT.
2. How about computing the whether a large det is zero or not. This can be done with large number package. Another idea is to do via many primes. Then invoke CRT to prove that if all primes are zero it must actually be zero.
Any other ideas?
Thanks, I will certainly use RSA computation using CRT.