Treebeard's Stumper Answer

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 believe there are just four ways (and their leftright 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 (n1)/2 arrangement of n rings for any odd n? Is a general solution or a betterthanbruteforce 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 GThe task is to find unique whole number values for {A .. I} so thatA+B = B+C+D = D+E+F = F+G+H = H+IThe 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 AI are just the numbers 19, 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)/5So, 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 <= 14So 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.
 No single digit can equal t since t>9.
 For any two digits, x+y=t, where would they go? x could not go in B or H, because then A or I would then have to be y and y has to be one of the intersections. But if x/y went in D/F, then E would have to be zero, which is not allowed.
 For any three digits, x+y+z=t, where would they go? Two of the three would have to be placed in the same ring, but then z couldn't be one of the intersections.
 All four digits can't sum to t since their sum must be divisible by five and no member of {11, 12, 13, 14} qualifies. There's another problem, since 5t = 45+(B+D+F+H). So if B+D+F+H = t, then 4t = 45, but that's not a whole number, so it's not allowed. Therefore B+D+F+H can't equal 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.)
 Sum t = 11.
Sum t = 11 = 9 + (B+D+F+H)/5, so (B+D+F+H) must equal 10.
The numbers {1,2,3,4} must be used for the intersections.
Some trial and error reveals the only solution. The outside intersections B or H can't be 1 because A or I would then have to be 10. So try D=1. If B were 4, then 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 since both C and I would then be 8; and if H=4 and F=3, then D+F=4, and both E and I would be 7. So B is not 2, it must be 3. If B+D=4, then H can't be 4. So the only choice is that H=2 and F=4. The remaining values can now be easily placed. Similar thinking applies for each of the answers.
Intersections:
B+D+F+H = 10
t = 9 + 10/5 = 11
Conflict with t=11
Solution:1+2+3+4 none 8 6 9 3 1 4 2 sum = 11 7 5
 Sum t = 12.
Sum t = 12 = 9 + (B+D+F+H)/5, so (B+D+F+H) must equal 15.
Here are the only ways to do it, and all the conflicts. There is no solution.
Intersections:
B+D+F+H = 15
t = 9 + 15/5 = 12
Conflict with t=12
Solution:1+2+3+9 3+9 = 12 1+2+4+8 4+4 = 12 1+2+5+7 7+5 = 12 1+3+4+7 1+4+7 = 12 1+3+5+6 1+5+6 = 12 2+3+4+6 2+4+6 = 12
 Sum t = 13.
Sum t = 13 = 9 + (B+D+F+H)/5, so (B+D+F+H) must equal 20.
Here are the only ways to do it, and the conflicts. There are two solutions.
Intersections:
B+D+F+H = 20
t = 9 + 20/5 = 13
Conflict with t=13
Solution:1+2+8+9 1/2 must be D/F, so E>9 1+3+7+9 1+3+9 = 13 1+4+6+9 4+9 = 13 2+3+6+9 none 7 8 4 6 2 3 9 sum = 13 5 12+4+5+9 4+9 = 13 1+4+7+8 1+4+8 = 13 2+3+7+8 2+3+8 = 13 1+5+6+8 3+8 = 13 2+4+6+8 none 7 3 9 6 2 8 4 sum = 13 5 13+4+5+8 5+8 = 13 2+5+6+7 6+7 = 13 3+4+6+7 6+7 = 13
 Sum t = 14.
Sum t = 14 = 9 + (B+D+F+H)/5, so (B+D+F+H) must equal 25.
Here are the only ways to do it, and the conflicts. There is one solution.
Intersections:
B+D+F+H = 25
t = 9 + 25/5 = 14
Conflict with t=14
Solution:1+7+8+9 Any two of {7,8,9} add to > 14 2+6+8+9 Any two of {6,8,9} add to >= 14 3+5+8+9 5+9 = 14 3+6+7+9 none 5 4 8 9 3 7 6 sum = 14 2 14+5+7+9 5+9 = 13 4+6+7+8 7+8 = 13 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 2n1 areas to fill with the numbers {1 .. 2n1}. There are (n+1)/2 areas above, (n1)/2 areas below, and n1 intersections. As above, the sum total of all n circles is:
nt = Sum(1 .. 2n1) + Sum{intersections} = (2n1)(2n)/2 + Sum{intersections} = n(2n1) + 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 givesSum{intersections} t = (2n1) +  nThis 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 {2n1, 2n2, 2n3, ...} with the first n1 terms in each case.(1+2+3+...+n1) t_{min} = (2n1) +  n (n1)n = (2n1) +  2n 1 =  (5n3) 2Similarly, with a bit more algebra:(2n1)+(2n2)+(2n3)+...+(2nn1) t_{max} = (2n1) +  n Sum{1 .. 2n1}  Sum{1 .. n} = (2n1) +  n (2n1)(2n)  (n)(n+1) = (2n1) +  2n 3(n1) = (2n1) +  2 1 =  (7n5) 2Note 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 n1 numbers whose sum is divisible by n. The set {1, 2, 3, .. n1} qualifies, and so does the set {2, 4, 6, .. 2n2}. So here's a general solution:
For n intersecting rings, fill in the n1 intersections with the following numbers in sequence:
n1, 2n2, n3, 2n4, n5, 2n6, n7, 2n8, ..., 2, 2n(n1)=n+1Now fill in the remaining circles from left to right so that each ring has a sum of 3n2. Another solution can be had by dividing each number by two and filling in the rings so each has a total of (5n3)/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 19Note 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 3Patterns 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:
 What if you give the chain of Olympic Rings a halftwist and join it end to end like a Moebius strip, or bring the last ring back over the top to intersect the first ring? (It comes to the same thing.) How many solutions are there? Can you analyze this problem now? Here's a hint!
 I first found this stumper in a post by Andrew Gray to the rec.puzzles Usenet group on March 23, 1997. I saved it for the Sydney 2000 Olympics. I learned a lot from Ken Duisenberg's Puzzle of the Week (POTW) solution to this stumper. This stumper is also discussed on Patrick De Geest's Nine Digits Page.
 How many ways are there to find 4 different numbers less than or equal to 9 that add up to 14? The answer is some degree of infinity if we allow decimals or fractions or negative numbers, but there's a definate answer (6) if we only consider whole numbers. This partition function is a bit like factoring into primes, but different, and harder. I wrote a DOS BASIC program to find integer partitions for my Millennium Magic (17 Dec 99) stumper, which also has links for more information on the math. This is a useful program for applying partition functions to stumpers like this. You can download PART2K for QBasic/QB/PDS from Treebeard's Basic Vault.
Back to Stumper
Last modified .