Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer18 December 1998

Holiday Magic

Put the numbers 1 to 12 on the holiday stars, trees, and wreaths shown below, with one number in each design, so they add up to the same sum in each of these seven ways:
• each of the two center columns (tree-wreaths-tree)
• each of the two center rows (star-wreaths-star)
• the four stars together
• the four trees together
• the four wreaths together
The magic sum must be 26. (Why?) How many different ways are there to solve this stumper?

The holiday stumper was to put the numbers 1 to 12 on the stars, trees, and wreaths so that each group, row, and column adds up to 26. Here's two different ways:

 ``` 1 12 9 8 5 4 3 6 7 10 11 2 ``` ``` 11 8 7 9 4 6 10 1 12 3 5 2 ```

I found these by trial and error. Then I wrote a computer program and found literally thousands of different solutions! The details are below.

Notes:

This stumper is problem 400 in Henry Ernest Dudeney's 536 Puzzles & Curious Problems (edited by Martin Gardner, 1967). I changed his Roses, Shamrocks, and Thistles to make it a holiday stumper.

It's clear that the magic sum must be 26. Consider just the two outside groups of stars and trees and the four rows and columns. Between them, each number {1 .. 12} is used twice to make six magic sums. Therefore 6 x sum = 2 x (1+2+3+...+12) = 156, and 156 / 6 = 26.

Many DMS parents and kids found different solutions to this stumper once they started looking. It became obvious that there are many solutions. But exactly how many? There are 12x11x10x...x1 = 12! = 479,001,600 different ways to arrange the numbers on the diagram. How many of these ways are solutions?

Graybear and I both went at this problem in totally different ways. I found a few solutions by hand and started to write BASIC computer programs. Graybear also found a few by hand and then found interesting ways to transform one solution into new ones. For example, he noticed that

For every group of four numbers adding to 26, two were > 6.5, and two were < 6.5. I realized that I could subtract 6 from the larger numbers and add 6 to the lower numbers to get a new solution.
Graybear's method is more analytic, but I think I found more solutions in the end. Graybear is still working on the problem, so the rest of this analysis is mine alone.

I think there are 13,952 solutions to the stumper. These fall into 75 families depending on which numbers are in the center (the wreaths). These in turn fall into 31 groups depending on the other numbers used (the stars and trees).

I began by finding all the ways to add four different numbers in the set {1 .. 12} and get a sum of 26. This is one of the things that mathematicians call a Partition Function. Partitioning is a bit like factoring in that it decomposes a number into parts, but it uses addition rather than multiplication. For more info on the math, check out Eric's Treasure Trove of Mathematics. (My problem is different from his P(n) and Q(n) functions because I add the constraint that all numbers are less than or equal to 12.)

These four-number tetrads are the only possible candidates for stars, trees, and wreaths. As a fun programming challenge, I wrote a small DOS/Win BASIC program that uses a recursive procedure to find the partitions of any number into any number of parts. You can download PARTITN.BAS for QBasic/QB/PDS.

I found that there are 33 tetrads that add four numbers less than or equal to 12 and get 26:

 12 , 11 , 2 , 1 12 , 10 , 3 , 1 12 , 9 , 4 , 1 12 , 9 , 3 , 2 12 , 8 , 5 , 1 12 , 8 , 4 , 2 12 , 7 , 6 , 1 12 , 7 , 5 , 2 12 , 7 , 4 , 3 12 , 6 , 5 , 3 11 , 10 , 4 , 1 11 , 10 , 3 , 2 11 , 9 , 5 , 1 11 , 9 , 4 , 2 11 , 8 , 6 , 1 11 , 8 , 5 , 2 11 , 8 , 4 , 3 11 , 7 , 6 , 2 11 , 7 , 5 , 3 11 , 6 , 5 , 4 10 , 9 , 6 , 1 10 , 9 , 5 , 2 10 , 9 , 4 , 3 10 , 8 , 7 , 1 10 , 8 , 6 , 2 10 , 8 , 5 , 3 10 , 7 , 6 , 3 10 , 7 , 5 , 4 9 , 8 , 7 , 2 9 , 8 , 6 , 3 9 , 8 , 5 , 4 9 , 7 , 6 , 4 8 , 7 , 6 , 5

Now we just have to find every combination of three of these tetrads that don't repeat numbers between them, and then try to arrange them as required by the stumper. I wrote another BASIC program to do this. It's not elegant, but I think it (finally!) works. You can download HMAGIC.BAS. In the end, it's frustrating that it only takes the computer a second or two to do the job. At least it should struggle some like Graybear and I did!

My program finds 32 different ways to select three tetrads (12 numbers) from the above list that each add up to 26 and don't repeat numbers between them. Here they are:

 12 , 11 , 2 , 1 10 , 9 , 4 , 3 8 , 7 , 6 , 5 12 , 11 , 2 , 1 10 , 8 , 5 , 3 9 , 7 , 6 , 4 12 , 11 , 2 , 1 10 , 7 , 6 , 3 9 , 8 , 5 , 4 12 , 11 , 2 , 1 10 , 7 , 5 , 4 9 , 8 , 6 , 3 12 , 10 , 3 , 1 11 , 9 , 4 , 2 8 , 7 , 6 , 5 12 , 10 , 3 , 1 11 , 8 , 5 , 2 9 , 7 , 6 , 4 12 , 10 , 3 , 1 11 , 7 , 6 , 2 9 , 8 , 5 , 4 12 , 10 , 3 , 1 11 , 6 , 5 , 4 9 , 8 , 7 , 2 12 , 9 , 4 , 1 11 , 10 , 3 , 2 8 , 7 , 6 , 5 12 , 9 , 4 , 1 11 , 8 , 5 , 2 10 , 7 , 6 , 3 12 , 9 , 4 , 1 11 , 7 , 6 , 2 10 , 8 , 5 , 3 12 , 9 , 4 , 1 11 , 7 , 5 , 3 10 , 8 , 6 , 2 12 , 9 , 3 , 2 11 , 10 , 4 , 1 8 , 7 , 6 , 5 12 , 9 , 3 , 2 11 , 8 , 6 , 1 10 , 7 , 5 , 4 12 , 9 , 3 , 2 11 , 6 , 5 , 4 10 , 8 , 7 , 1 12 , 8 , 5 , 1 11 , 10 , 3 , 2 9 , 7 , 6 , 4 12 , 8 , 5 , 1 11 , 9 , 4 , 2 10 , 7 , 6 , 3 12 , 8 , 5 , 1 11 , 7 , 6 , 2 10 , 9 , 4 , 3 12 , 8 , 4 , 2 11 , 9 , 5 , 1 10 , 7 , 6 , 3 12 , 8 , 4 , 2 11 , 7 , 5 , 3 10 , 9 , 6 , 1 12 , 7 , 6 , 1 11 , 10 , 3 , 2 9 , 8 , 5 , 4 12 , 7 , 6 , 1 11 , 9 , 4 , 2 10 , 8 , 5 , 3 12 , 7 , 6 , 1 11 , 8 , 5 , 2 10 , 9 , 4 , 3 12 , 7 , 6 , 1 11 , 8 , 4 , 3 10 , 9 , 5 , 2 12 , 7 , 5 , 2 11 , 10 , 4 , 1 9 , 8 , 6 , 3 12 , 7 , 5 , 2 11 , 8 , 6 , 1 10 , 9 , 4 , 3 12 , 7 , 5 , 2 11 , 8 , 4 , 3 10 , 9 , 6 , 1 12 , 7 , 4 , 3 11 , 9 , 5 , 1 10 , 8 , 6 , 2 12 , 7 , 4 , 3 11 , 8 , 6 , 1 10 , 9 , 5 , 2 12 , 7 , 4 , 3 11 , 8 , 5 , 2 10 , 9 , 6 , 1 12 , 6 , 5 , 3 11 , 10 , 4 , 1 9 , 8 , 7 , 2 12 , 6 , 5 , 3 11 , 9 , 4 , 2 10 , 8 , 7 , 1

Each of these 32 groups represents at least three potential solutions, since each of the three tetrads can potentially be in the position of the center wreaths. I had trouble with my program because I assumed that the results were more symmetrical than they actually are. In fact, my program finds that the results are complex. My program tests all combinations of the numbers in each combination of tetrads to find solutions to the stumper, and finds that:

• 14 of the groups allow each of the 3 tetrads to be in the center for a solution,
• 16 of the groups only allow 2 of the tetrads to be in the center for a solution,
• 1 of the groups only allows 1 of the tetrads to be in the center for a solution,
• 1 of the groups allows no solution.
The odd group of tetrads with just one solution is number <31>:
 12 , 6 , 5 , 3 11 , 10 , 4 , 1 9 , 8 , 7 , 2
With this group, the first tetrad {12, 6, 5, 3} must be in the center wreaths.

The very odd group of tetrads with no solutions is number <16>:

 12 , 8 , 5 , 1 11 , 10 , 3 , 2 9 , 7 , 6 , 4
Try it and you'll see why it doesn't work. No matter how you arrange the numbers, you always need a sum that you can't get with what's left.

The complete list of 75 solutions is long. You can view it in a separate text file.

There's actually many more solutions than that! Each of the 75 solutions in 31 (of 32) groups of unique tetrads is the basis of a family of either 128 or 256 different solutions made by rotating and exchanging the different numbers. Graybear explains the process like so:

The first solution I stumbled across is:
```        1 12
9  8  5  4
3  6  7 10
11  2
```
The following numbers in this arrangement can be independently swapped to provide new solutions: 1 and 11, 2 and 12, 9 and 4, and 3 and 10. This gives 2^4=16 solutions. Each solution can be rotated four ways, then flipped (i.e. mirror-imaged) and rotated four more ways. This gives 16 x 8 = 128 solutions.

The 9 and 4 can be swapped with the 3 and 10 to give:

```        1 12
3  8  5 10
9  6  7  4
11  2
```
This can go through the above process again to give another 128 solutions for a total of 256.
The second swap can only happen if both rows or columns of the center tetrad (the wreaths) add up to 13, as they do above. But this is not always possible. In all the families of solutions my program found, this is possible in 34 families, but it's not possible in 41 families.

The final tally is therefore:

```      34 x 256 =  8,704
+ 41 x 128 =  5,248
-------------------
75 total = 13,952 solutions
```
That's how many solutions there are, if my program is doing its job. That's just 0.0029% of the 12! possible arrangements. No wonder it's a stumper!

It's an ancient debate whether math is based on invention or discovery. I definately discovered this result. I think there's deep math in problems like this that involve additive partitions. Decomposing numbers into prime factors is the basis for most number theory. By comparison, it's my impression that partition theory based on addition is little studied. This was just a silly (but compelling!) brain teaser, but it exposes interesting patterns worth further study.

For further study, check out:

Back to Stumper