Skip to content

Zack’s Mom Knows

January 25, 2014


A puzzle with a story

Unknown

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 {\dots}

The Puzzle

The problem is an innocent question about labeling a hexagon. The problem is to assign the integers {1,2,\dots,12} 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 {19}. 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 {19}. 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 {19}. 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 {12!} is large, but not impossible for a laptop to handle. I thought that a search could be done more like

\displaystyle  \binom{12}{6} 6! 6!,

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 {G=(V,E)}, find a labeling of the edges and vertices with the numbers

\displaystyle  1,2,\dots, |V|+|E|,

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 {20}, but there are solutions with common value {19} also.

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 {35} vertices. It is called the graceful graph conjecture—see here. And good luck.

[fixed typo]

About these ads
14 Comments leave one →
  1. Joseph permalink
    January 25, 2014 10:38 pm

    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. :-)

    • January 26, 2014 3:00 am

      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.

  2. January 26, 2014 12:25 am

    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

  3. msk2 permalink
    January 27, 2014 10:04 am

    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)

  4. January 27, 2014 4:51 pm

    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

  5. January 29, 2014 4:58 am

    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.

    • January 31, 2014 3:00 am

      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.

    • February 1, 2014 11:21 pm

      It is also possible to generalize this problem to any n-gon for n greater than 2.

    • February 2, 2014 4:15 am

      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.

  6. January 31, 2014 2:57 am

    And a practical application is?

    • rjlipton permalink*
      January 31, 2014 12:07 pm

      Qasim

      One of refs claims network application for labels, but unclear to me

      • January 31, 2014 12:21 pm

        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.

  7. rjlipton permalink*
    January 31, 2014 12:34 pm

    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?

    • January 31, 2014 12:41 pm

      Thanks, I will certainly use RSA computation using CRT.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,544 other followers