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 problem is an innocent question about labeling a hexagon. The problem is to assign the integers to the twelve vertices and edges of the hexagon, so each number is used exactly once. So far pretty easy: there are six edges and six vertices so twelve numbers is just right. The catch—the reason it is a “puzzle”—is that the each edge must have the same “magic sum.” The magic sum is the sum of the numbers assigned to the edge plus the numbers assigned to its two endpoint vertices.
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 . He then used a kind of simulated annealing to find the solution. He put the twelve numbers down, then moved them to reduce the number of bad edges, ones with a sum different from . He did this by hand, and was eventually able to solve the problem. He did not tell us whether he found the solution in seconds, minutes, or hours.
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 . Noga had some idea that sounded likely to pin this down, yet we could not finish it. Noga also suggested that you could “write a program.” Indeed is large, but not impossible for a laptop to handle. I thought that a search could be done more like
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.
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 , find a labeling of the edges and vertices with the numbers
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.
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 , but there are solutions with common value also.
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 vertices. It is called the graceful graph conjecture—see here. And good luck.