Ken's POTW


Olympic Ring Addition
Given the five olympic rings how can the digits one through nine be placed within the nine regions (five non-overlapping ring regions and four overlapping regions shared between two rings) so that each ring contains the same total?

Or alternatively, using the labels A through I for the regions, how can the numbers one through nine be assigned to the variables such that:

A+B = B+C+D = D+E+F = F+G+H = H+I

Is there a logical approach other than brute force?

Source: Andrew Gray in newsgroup rec.puzzles, March 23, 1997.


Solution: I received a few programmed solutions from Kirk Bresniker and Hayim Even-Zohar, and a "brute force" solution from Jon Abraham, Sorin Ionescu, and Neena Rao. The one "brute force" solution is the first below. Craig Gentry's method (shown below) added the second. Bert Sevenhant sent the final of the four possible solutions (His description follows Craig's below.) Following these two solutions is my own solution.
A+B B+C+D D+E+F F+G+H H+I
9+2 2+5+4 4+6+1 1+7+3 3+8 Sum=11
9+4 4+1+8 8+3+2 2+5+6 6+7 Sum=13
7+6 6+5+2 2+8+3 3+1+9 9+4 Sum=13
8+6 6+1+7 7+4+3 3+2+9 9+5 Sum=14

Craig Gentry sent the following analysis 8/18/97. He points out it only finds two of the four solutions. (Notice, he doesn't actually say what those solutions are...) It's interesting how generic this solution is, though.
The following methods generate 2 distinct (not simply reversals of each
other) solutions for n rings, where n is any given odd number.  Although
I haven't checked, I doubt that they generate every solution.
        In the n-1 regions of intersection, place the following numbers
sequentially:
        n-1, 2n-2, n-3, 2n-4, n-5, 2n-6, n-7, 2n-8,..., 2, 2n-(n-1)=n+1.
Notice that all of the above numbers are even.  Fill in the remaining
regions so that each ring has a total of 3n-2.
        You can get a second solution by dividing all the numbers in the above
sequence by 2, placing the resulting sequence in the regions of
intersection, and the filling in the remaining regions so that each ring
has a total of (5n-3)/2.
        Suppose, for example, you have nine rings.  Using the above methods,
you get the solutions:
        17, 8, 1, 16, 3, 6, 5, 14, 7, 4, 9, 12, 11, 2, 13, 10, 15  and
        17, 4, 9, 8, 10, 3, 11, 7, 12, 2, 13, 6, 14, 1, 15, 5, 16.

Here are some of the thoughts that led these methods.  First, if t is
the total in each ring, then
        tn = 1+2+3+...+(2n-2)+(2n-1) + i_1 + i_2 +... + i_(n-1)
           = n(2n-1) + i_1 + i_2 +... + i_(n-1),
where i_x is the region of intersection between the xth and (x+1)th
rings.  Therefore, the sum of the numbers in the regions of intersection
must be divisible by n.  The first set of n-1 numbers the sum of which
is divisible by n (odd) that came to my mind was 1, 2, 3,... n-1. 
Obviously the set 2, 4, 6,... 2n-2 also works.  After that, it was just
a matter of ordering the set in a sensible way.  Clearly many other sets
of n-1 numbers have a sum that is divisible by n, but I haven't tested
whether these sets generate solutions.
-Craig Gentry

Bert Sevenhant, who runs his own puzzle page, sent the following abridged solution:
I could give you the full proof but this would be to long.
My idea is as follows.
1. 45 + B + D + F + H = 5 -tuple
this leaves 1+2+3+4=10,..,30=6+7+8+9 as possibilities.
2. We only consider A < I ( and B < H), since the problem is symmetric.
3. for each sum we now exclude the numbers X,Y that can't be B or H :
For 3 possible reasons (If n=the sum of each ring)
X < n - 9 
2X = n
X+Y=n.
It seems that in each case at least 1 number drops so this narrows down
the possibilities.
4. Now we try to find the numbers for the two not outer, not cntral rings
(so C,D ,F and G) For example if A = 7 then C+D=7, search for every
possible c,d. There are 2 reasons why this could be impossible : "already
used" and none or both have to be in {B,D,F,H}.
This considerations and some work lead to the answer I gave.

My (Ken's) solution isn't pretty, but is "logical":

We want:

A+B = B+C+D = D+E+F = F+G+H = H+I

The sum of all five circles is:
5S = A + ... + I + B + D + F + H

Since A-I are 1-9, this is the same as
5S = 45+B+D+F+H
S = 9 +(B+D+F+H)/5

So, (B+D+F+H) must be divisible by 5. It can range from 10 [1,2,3,4] to 30 [6,7,8,9], and the corresponding sum for each circle, S, can range from 11 to 15, respectively.

First notice that no combination of (B,D,F,H) can sum to S. For one digit, it's not possible. For all four, it's not possible due to the definition.

For two, (x+y=S) consider where they'd be placed: x could not be put in B/H, because A/I would have to be y, but y has to be in (B,D,F,H). So they would have to go in D and F, but that would make E=0.

For three, (x+y+z=S), two of the three (say x,y) would have to be placed together, but that would force z to not be in (B,D,F,H) - a contradiciton.

S = 11
A   E   I
 B D F H
  C   G

8   6   9
 3 1 4 2
  7   5 
For S=11, (B+D+F+H) = 10, the numbers [1,2,3,4] must be used, and the contradictions above don't apply. '1' cannot be on the outside (B or H) because A or I would have to be 10. So let D=1. If B were 4, [F,H] would be [2,3] and both C and G would have to be 6; so B is not 4. If B were 2, then B+D=3, so H could not be 3 (both C and I would be 8); but with H=4 and F=3, D+F=4, and both E and I would be 7; so B is not 2. B is 3. With B+D=4, H is not 4; so H=2 and F=4. The remaining values can now be easily placed. Similar arguments apply for answers found below, too.

S=12.
For S=12, (B+D+F+H)=15, there is no solution. The possible combinations and related concerns are below:
BDFHConflict
12xyx+y=12
3xyzx+y+z=12
14xy, xy>41+4+x+y>15

S=13.
For S=13, (B+D+F+H)=20. The possible combinations and related concerns are below:
BDFHConflict
1289(1,2) must be (D,F), so E=10.
xy7zx+y+z=13
14694+9=13
15685+8=13
2369None - this works:
7   8   4
 6 2 3 9
  5   1
24594+9=13
2468None - this works:
7   3   9
 6 2 8 4
  5   1
34585+8=13

S=14.
For S=14, (B+D+F+H)=25. The possible combinations and related concerns are below:
BDFHConflict
1xyzAny two of (xyz) sum to S>14.
2xyzAny two of (xyz) sum to S>=14.
35895+9=14
3679None - this works:
5   4   8
 9 3 7 6
  2   1
45795+9=14
46786+8=14

S=15.
For S=15, (B+D+F+H)=30, so (BDFH) must be (6789) and 6+9=7+8=15, so there are no solutions.


Mail to Ken