## Sunday, September 13, 2009

### From 1 Through 19

The Problem

I found the following puzzle in a book called the Moscow Puzzles by Boris A. Kordemsky. (It's problem number 34, which you can also find at Google books.)

Write the numbers from 1 through 19 in the circles so that the numbers in every 3 circles on a straight line total 30.
Take a minute to try and solve it on your own before reading on. (It's not that hard, so it really should take just a minute or so.)

The Solution

The key to this puzzle is figuring out which number goes in the center. It's easy to show what numbers can't be in the center. The 1 can't be in the center because, although there are a few combinations you can come up with that add up to 30, there aren't enough with 1 in the center position. You could have the combinations

19, 1, 10
18, 1, 11
17, 1, 12
...

But you'll soon be left with numbers too small to form a group that sums to 30. For example, what number do you place across from the 2?

There aren't any numbers large enough to fill the third spot in this combination. You can try placing each of the numbers from 1 through 9 in the center and find the same shortcoming.

Similarly, the number 19 is too large to go in the center. There's no number you can place opposite the 18. In fact the sum of 18 and 19 is already too large, even without a number in the opposite circle.

Through trial and error, you can find that all of the numbers from 11 through 19 are too large.

That leaves only the number 10 to occupy center position. After that, all of the other numbers fall into place.

A Challenge

A magic square is an arrangement of n2 distinct integers (from 1 to n2) in a square such that the n numbers in each row, each column, and in the two long diagonals all have the same sum.

Using the principles from the solution to the From 1 Through 19 puzzle above, can you construct a 3 x 3 magic square?

I'll give you the additional piece of information that each row, column, and diagonal must add to the sum of 15 (to save you the trouble of looking it up on Wikipedia, which would be cheating.)

I'll have the complete solution in an upcoming post.

MaJJ said...

We had to find 3x3 magic ring in Klokan (math competition for primary schools - czech version of http://www.mathcomp.leeds.ac.uk/ ). It was basically trial and error, but this is interesting - does the number in the middle have to be average of the set of numbers you can pur there? E.g. for numbers 1-9 it would be 5? And in your example it'd be 10?

Bill the Lizard said...

MaJJ,
The number in the middle does have to be 5, but unlike the From 1 Through 19 puzzle, the challenge isn't over once you've found that out. Not just any number can go in the corners or on the sides.

There are a couple of interesting points you bring up. One is concerning solving the magic square using trial and error. With a small instance of the puzzle, like 3x3, it's certainly possible to solve it that way. Naturally, trial and error will be much less effective with larger grids. Also, there's a very nice way to solve the puzzle using logical steps that I'll show you in an upcoming post (if you haven't already gotten it by then).

The other interesting point you brought up is that the center position is occupied by the average of the set of numbers in the puzzle. I hadn't considered that before, and I'll have to investigate a little to see if there's a mathematical relationship that says the center position has to be the average value, or if that's just a coincidence. Thank you for bringing it up, and thanks for reading!

MaJJ said...

Well, NOW I'm trying it again and ... it reminds me of kakuro :) What I'm doing is writing down 3-number combinations with the sum of 15.

So:

9+5+1, 9+4+2
8+6+1, 8+5+2, 8+4+3
7+6+2, 7+5+3
6+5+4
(I believe that's all of them - of course, there is for example 1+5+9, but it's already there, just in different order.)

So ... you start with the 5 in the middle - using the logics in your post - if I can find a combination which doesn't fit the conditions (say, 1+4+x), I know that 4 can't be in the middle.

Then it's all about two choices - and it nests... Looks like a nice programming puzzle with recursion :)

Let's say I start with the first combination on the list. I can put it there in two ways:

9 _ _ ... _ _ _
_ 5 _ ... 9 5 1
_ _ 1 ... _ _ _

I'll try the first one.
In the list of combinations I see that number 9 has one more combination - 9+4+2. So now I have two options:

9 4 2 ... 9 2 4
_ 5 _ ... _ 5 _
_ _ 1 ... _ _ 1

But I see that in both of them I can't put anything to the right of the 5. So if both options fail, the "parent" option fails too. That puts us back into:
_ _ _
9 5 1
_ _ _

Now let's try that 9+4+2 thing again:
4 _ _
9 5 1
2 _ _ is the only option.

And because the diagonal can be filled now, we have:
4 _ _
9 5 1
2 _ 6

And again, we can fill another row:
4 _ _
9 5 1
2 7 6

And again :)
4 3 _
9 5 1
2 7 6

And we're done.
4 3 8
9 5 1
2 7 6

MaJJ said...

Just an additional note: By the nice way to solve the puzzle you probably mean the Siamese method (http://en.wikipedia.org/wiki/Siamese_method)... But I have no clue why it works :D

Bill the Lizard said...

MaJJ,
The method I'm thinking of isn't a straight algorithm like the Siamese method (which, by the way, I don't understand why it works either), but a logical approach that relies more on the kind of process-of-elimination type of reasoning that you'd use to solve Sudoku (or, as you mentioned, Kakuro) puzzles. It's actually not that far removed from the method you showed in your second comment.

Zach said...

8 1 6
3 5 7
4 9 2

In the circle problem there was an odd number of circles and the value that belonged in the middle was the first whole number above the 1/2 the total numbers. It was the same here, there were 9 numbers, the largest in the middle should be 5 (next largest whole number above 9/2 or 4.5). After that the rest of the numbers fall into place, starting with 1,5,9 and going around the circle plugging in the pairs that add up to 10 around the outer edge.

Mouk said...

For the first problem there is a better way than the trial and error method. It can be solved systematically. What we have here is 9 lines of numbers and each line sums up to 30. Summing them all we get 270.
On the other hand summing all number from 1 to 19 results in (19 * 20)/2 = 190. The number in the middle appears 9 times in the first sum but only once in the second. Thus 8*x = 270 – 190= 80 => x = 10.

X ,the number in the middle should be 10.

Matt said...

I decided it had to be 5 because of reductio ad absurdum:
- Assume the center is less than 5. The biggest number the 1 can be paired with is 9, but that triplet adds up to less than 15.
- Assume the center is more than 5. The smallest number the 9 can be paired with is 1, but that triplet adds up to more than 15.

The square is symmetrical over both horizontal and vertical reflection, and over 90 degree rotation, so when trying to decide where to place the 1, it's either in a corner or not.

If we place 1 in a corner, we need to come up with two more pairs of numbers that add up to 14. 6 and 8 works, but 7 and 7 does not, so 1 can't be in the corner, so we put it in the center of the top row.

This means a 9 in the bottom center. 1 has to be flanked by 6 and 8, which means 9 is flanked by 2 and 4. Addition says 7 goes between the 2/6, and 3 goes in between the 4/8.

Bill the Lizard said...

Matt,
Nice. That's really close to the same process I went through to solve it. Just about the only thing I can add now are pictures. :)

Anonymous said...