Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
22 September 2000

Olympic Number Rings

With our Catalina trip, and school underway, it’s been hard to find time to follow the Olympic Games. My favorites are the track and field events and the odd events like air gun shooting. Here’s another odd Olympic challenge. The Olympic logo consists of five overlapping rings that form nine separate areas, four of them shared between different rings. The stumper is to place the numbers 1 to 9 in these nine areas so that each complete ring has the same sum. This should be easy with these small numbers! How many different solutions are there?

I've numbered the 9 regions in order from left to right, but this numbering does not work for
the stumper. The top-left ring has a sum of 1 + 2 = 3, and the top-middle ring has a sum of
4 + 5 + 6 = 15. The challenge is to arrange the digits so that each ring has the same sum!

I believe there are just four ways (and their left-right reflections) to put the numbers 1 to 9 in the nine areas of the Olympic logo so that each ring has the same sum. Eight DMS students found solutions, starting with Tessa. There are some interesting regularities in these numbers. For example, the first number on either end is always the sum of the third and fourth numbers from the end. Brute force is all it takes to find these solutions, but some analysis helps us see farther. The details are below.

Notes:

I think I can prove that these are the only four solutions (with their reflections) to the Olympic Number Rings stumper. But what about 2x1 rings, or 4x3, or 5x4, or any (n+1)/2 by (n-1)/2 arrangement of n rings for any odd n? Is a general solution or a better-than-brute-force computer program possible? I'm thinking about this stumper in a general way, since much of this analysis can be extended to any odd number of rings. (In this case n = 5 rings.)

Label the areas like this: 

  A   E   I
   B D F H           <- the intersections
    C   G
The task is to find unique whole number values for {A .. I} so that 
  A+B = B+C+D = D+E+F = F+G+H = H+I
The sum total t of all five circles is: 
  5t = (A+B) + (B+C+D) + (D+E+F) + (F+G+H) + (H+I)
     = (A+B+C+D+E+F+G+H+I) + (B+D+F+H)
Since A-I are just the numbers 1-9, and 1+2+3+4+5+6+7+8+9 = 45, this is the same as: 
  5t = 45 + (B+D+F+H)
   t =  9 + (B+D+F+H)/5
So, the sum of the intersections (B+D+F+H) must be divisible by 5, the number or rings in the original problem. This sum can range from 10 [1,2,3,4] to 30 [6,7,8,9], and the corresponding sum for each circle t can range from 11 to 15, respectively.

In fact the highest sum of 15 is not possible, as Greybear found with a different tack. Consider just the upper three circles: 

  3t = (A+B) + (D+E+F) + (H+I)
     = (A+B+C+D+E+F+G+H+I) - (C+G)
     = 45 - (C+G)
The smallest possible sum for C+G is 1+2 = 3, and the largest possible sum is 9+8 = 17, so: 
   3 <= C+G <= 17
  28 <= 3t  <= 42
  10 <=  t  <= 14
So t must be a member of {11, 12, 13, 14}. Note how we've changed the original problem to a partition question: how many ways are there to add four different numbers from the set {1 .. 9} and get a result divisible by 5? These constraints narrow the choices considerably, but we can narrow them even further because no combination of the intersection numbers {B, D, F, H} can add up to the sum t.

Now we have a powerful toolkit in place and can search for solutions for the number ring sum t = {11, 12, 13, 14}, though the details are tedious. I got the partition data from my PART2K.BAS program, which I wrote for another stumper. (There's a download link at the end.)

This proves that these are the only four solutions (with their reflections) for n=5 rings. How much of this can be generalized for different (odd) numbers of Olympic Number Rings? Lots, but not everything.

If there are n rings, then there are 2n-1 areas to fill with the numbers {1 .. 2n-1}. There are (n+1)/2 areas above, (n-1)/2 areas below, and n-1 intersections. As above, the sum total of all n circles is: 

  nt = Sum(1 .. 2n-1) + Sum{intersections}
     = (2n-1)(2n)/2 + Sum{intersections}
     = n(2n-1) + Sum{intersections}
I'm using the useful formula that Sum{1 .. n} = 1+2+3+...+n = n(n+1)/2. (Kids, you should know this one!) Dividing by n gives 
                Sum{intersections}
   t = (2n-1) + ------------------
                         n
This shows that the sum of the numbers in the intersections must be divisible by n. It also gives a general way to figure the smallest and largest sums t, since the smallest sum will occur with the intersections filled with {1, 2, 3, ...} and the largest sum will occur with the intersections filled with {2n-1, 2n-2, 2n-3, ...} with the first n-1 terms in each case. 
                  (1+2+3+...+n-1)
   tmin = (2n-1) + ---------------
                         n

                   (n-1)n
        = (2n-1) + ------
                     2n

          1
        = - (5n-3)
          2
Similarly, with a bit more algebra: 
                  (2n-1)+(2n-2)+(2n-3)+...+(2n-n-1)
   tmax = (2n-1) + ---------------------------------
                                n

                   Sum{1 .. 2n-1} - Sum{1 .. n}
        = (2n-1) + ----------------------------
                                n

                   (2n-1)(2n) - (n)(n+1)
        = (2n-1) + ---------------------
                           2n


                   3(n-1)
        = (2n-1) + ------
                     2

          1
        = - (7n-5)
          2
Note that these sums will always be whole numbers given odd n. Substituting n=5 gives smallest and largest sums of 11 and 15, which matches our earlier result. (Is the actual largest sum always one less than the calculated maximum?)

The most useful constraint in the n=5 example is that no combination of the intersections can add to the sum. But I don't see why this must be true in the general case; and in fact it's not true, as I'll show below. Graybear found some other interesting patterns in all the n=5 solutions: 

  a = c + d
  b + c = e + f
  d + e = g + h
  f + g = i        and, in larger patterns,
  f + g = i + j
  h + i = k + l
  j + k = m + n

  or, in more mathematical notation:
    x(n) + x(n+1) = x(n+3) + x(n+4)
But these patterns don't always hold in the n=11 solutions I give below. This makes me think there are more general constraints that would be useful for a computer program.

Even without these constraints, there is a method to find a solution (actually two). We need to fill the intersections with n-1 numbers whose sum is divisible by n. The set {1, 2, 3, .. n-1} qualifies, and so does the set {2, 4, 6, .. 2n-2}. So here's a general solution:

For n intersecting rings, fill in the n-1 intersections with the following numbers in sequence: 

  n-1, 2n-2, n-3, 2n-4, n-5, 2n-6, n-7, 2n-8, ..., 2, 2n-(n-1)=n+1
Now fill in the remaining circles from left to right so that each ring has a sum of 3n-2. Another solution can be had by dividing each number by two and filling in the rings so each has a total of (5n-3)/2 (the minimum sum).

I think this method will always find 2 answers. For example, with 11 rings, there are these two solutions to be had by "running the numbers": 

  21        3        7       11        15         19
    10   20   8   18   6   16   4   14    2    12       sum = 31
       1        5        9        13        17 


  21       12       14       16        18         20
     5   10   4    9   3   8    2    7    1     6       sum = 26
       1        13      15        17        19
Note in the second solution, 10+9+1+6 = 26, so it's not true in general that no combination of intersectors can add to the magic sum. This method also finds the only two solutions for three rings: 
  5       3    
    2   4      sum = 7
      1        

  5       4    
    1   2      sum = 6
      3

Patterns and questions abound here! But without additional constraints, a computer program will still be largely brute force, working from a partition function routine that finds Q(n,m,p), all the ways to add m unique numbers that are less than or equal to p and get a sum of n, and then testing all combinations. I already have that routine in my PART2K.BAS program. I'll get to this when I find time and a bit more inspiration!

Here are some ideas and links for further research:

Back to Stumper

Last modified .

Copyright © 2000 by Marc Kummel / mkummel@rain.org