Author |
Topic: Magic Hexagon (Read 1544 times) |
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
I am back after a long time and a good trip to India. So my friends popped me up a puzzle and it has been real tough to get it solved. Look at the attached picture.
The goal of this puzzle is to place a number into each dot and have every edge sum to the same number. In each circle, enter a whole number no less than 1 and no greater than 28. Use each number exactly once. The 9 colored dots must contain a prime number.
The only thing I have seen so far is brute forcing it. I would love to see a systematic approach to this just like our magic square.
|
|
 IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
 |
Re: Magic Hexagon
« Reply #1 on: Jan 25th, 2005, 7:55pm » |
 Quote  Modify
|
Here's a start...
:
Let magic sum = x
Let the numbers at the nodes with 3 edges be a,b,c,d
There are a total of 15 sides.
Sum of the first 28 integers = 406
Sum of the first 9 primes = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 100
If we sum the sides we count all the primes twice and {a,b,c,d} three times.
So
15x = 406 + 100 + 2(a + b + c + d)
= 506 + 2(a + b + c + d)
The only possible solutions are:
x = 36, a + b + c + d = 17 (actually impossible)
x = 38, a + b + c + d = 32
x = 40, a + b + c + d = 47
x = 42, a + b + c + d = 62
x = 44, a + b + c + d = 77
x = 46, a + b + c + d = 92
Of the 19 non-primes, 6 are odd and 13 are even.
|
| « Last Edit: Jan 30th, 2005, 3:55am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Magic Hexagon
« Reply #2 on: Jan 25th, 2005, 8:21pm » |
Quote Modify
|
Better check your signs:
15*32 = 480
506 + 2*13 = 532
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #3 on: Jan 25th, 2005, 11:14pm » |
Quote Modify
|
Thanks, Icarus. 
I have amended the post.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
asterix
Guest
|
Carrying on Thud's last comment
Try labeling all the points odd or even.
The total must be even, so every set of three has 0 or 2 odds.
First the 2. only two possible positions, not counting rotation and symmetry equivalents. One of the two will easily be seen to be impossible. The other, if I'm correct, only has three possible placements of the missing 6 odds. Of the three, one would make all a,b,c,d all odd, one would make them all even, one would make 2 even and 2 odd. (I think I was quickly able to eliminate the all odd solution, but I could be wrong). So a+b+c+d must be even, and x must be 38, 42, or 46.
Somebody tell me if I messed up here
|
|
IP Logged |
|
|
|
asterix
Guest
|
I did mess up. Trying again: if the number 2 is placed in one of the 3 outermost corners there is one possible placement of the 6 missing odds. I'd ruled that out because I was thinking there were 5 missing (in the other 2-placement an odd was forced next to the 2 and forgotten).
So in this scenario, a,b,c,d will be all odd, and x is limited in the same way as before
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #6 on: Jan 28th, 2005, 11:29pm » |
Quote Modify
|
:Running with asterix's idea, assume that the number 2 is at one of the three red nodes that are each connected to two other red nodes. Then 2's white neighbours will both be odd. And four even numbers must lie between the other six primes. So we are left with 13 non-primes, 4 odd and 9 even.
Because all sides must contain either 0 or 2 odd numbers, all of {a,b,c,d} must be odd,
and therefore a + b + c + d must be even.
Hence we can rule out
x = 40, a + b + c + d = 47
and
x = 44, a + b + c + d = 77
Also, {a,b,c,d} must be a subset of {1,9,15,21,25,27}
Hence
the minimum value of a + b + c + d = 46
and
the maximum value of a + b + c + d = 88
So we can rule out
x = 38, a + b + c + d = 32
and
x = 46, a + b + c + d = 92
This leaves
x = 42, a + b + c + d = 62
as the only possible solution.
So we must have either
1 + 9 + 25 + 27 = 62
or
1 + 15 + 21 + 25 = 62
But which of these numbers is at the central node?
In the 1st case,
it can't be 1 or 9 because 42 - 1 - 9 > 28
and
it can't be 25 or 27 because 25 + 27 > 42
Hence the 1st case is inadmissible.
In the 2nd case,
it can't be 21 or 25 because 21 + 25 > 42
Hence it must be 1 or 15
So far, so good.
But now we need
both the numbers not in {a,b,c,d} + 2 + a prime (< 28) to separately sum to 42
In the 2nd case, these numbers are 9 and 27
But 42 - 2 - 9 = 31 (a prime > 28)
Hence the 2nd case isn't admissible either.
So we are forced to conclude that the original premise is false.
:
Can anybody find anything wrong with the above?
|
| « Last Edit: Jan 29th, 2005, 12:37am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Magic Hexagon
« Reply #7 on: Jan 29th, 2005, 4:08pm » |
Quote Modify
|
I could find no fault with your excellent reasoning, T&B.
BTW, how did I miss this problem?
So...
::
The 2 must be placed at one of the end red nodes.
In which case only one odd needs to be used on an external edge node (between 2 and another prime). That leaves 5 odds to be distributed elsewhere.
W.L.O.G, suppose that 2 is next to d.
a,b,c must all be odd, leaving 3 odds.
If d were even, the node between d and 2 must be even, whereas the other middle node (between d and the prime) must be odd. But then we have one extra odd with nowhere to go.
So d must be odd, as must the node between 2 and d.
Hence we use T&B's arguments from before, and by removing all the impossible cases we arrive at the final possibility: the central node can be 1 or 15, and {21,25} plus the other one to be placed at the other triple count nodes.
If 15 is placed in the centre then 42-15-25=2, but 2 has been used on the external ring.
Therefore we conclude that 1 must be placed in the centre node, and the other triple count nodes contain {15,21,25}.
However, we now encounter a final contradiction. Consider the node between d and 2:
It cannot contain 21 as 42-21-2=19 and this is prime.
It cannot contain 15 or 25, as 42-2-15=25 and 42-2-25=15.
Hence there is no solution to the problem.
::
Now you'll need to check my reasoning.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #8 on: Jan 29th, 2005, 8:39pm » |
Quote Modify
|
Sir Col, I had previously come to the same negative conclusion, but (Gauss-like) was reluctant to post it.
on Jan 25th, 2005, 9:34am, Sameer wrote:
The only thing I have seen so far is brute forcing it. |
|
Yet Sameer's wording seems to indicate there is a solution.
|
| « Last Edit: Jan 30th, 2005, 3:50am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Magic Hexagon
« Reply #9 on: Jan 30th, 2005, 2:06am » |
Quote Modify
|
I thought the same, but then I wondered if the brute forcing had concluded there were no solutions and, uneasy with that result, he wanted to see if it could be analytically shown that no solution exists. Maybe he worded it in such a way so as to not form any bias in our approach?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #10 on: Jan 30th, 2005, 2:50am » |
Quote Modify
|
Quote:| Maybe he worded it in such a way so as to not form any bias in our approach? |
|
Yeah, if he had asked, 'Can anybody prove there are no solutions?', I don't think he would have had any takers.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
asterix
Guest
|
Am I a step behind everybody else? I'm wondering why the assumption that a,b,c,d must all be odd. Call the three hexagons A (left), B (right), and C (lower), and number the points as clock points.
I put the 2 at C8. and an odd at C7.
The remaining 5 odds could be at
A1, A7, B11, B5, and C3, making a,b,c and d all even.
Or put odds at
A2, A3, A7, B6, and B7, making a,b odd, c,d even.
I haven't worked through either of these scenarios completely, but are they possible?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #12 on: Jan 30th, 2005, 11:38am » |
Quote Modify
|
Yes, well done, asterix; the first combination is possible. (Haven't tried the second one.)
Yeah, I knew this was the weak link in the argument but, after playing with it for a while, I still couldn't find a configuration that worked out.
It looks like it is now more difficult to find {a,b,c,d}, as there are more even numbers to choose from than there were odd previously. Also, we cannot immediately eliminate the cases x = 38 and x = 46, as we did before.
|
| « Last Edit: Jan 30th, 2005, 11:46am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Magic Hexagon
« Reply #13 on: Jan 30th, 2005, 11:47am » |
Quote Modify
|
Good spot, asterix; both scenarios work fine.
I take it you're happy with T&B's case (2 placed on middle of three reds) though?
The problem now is that, using the case where {a,b,c,d} are all even, the minimum sum is 28 and the maximum sum is 100. This means that none of the possible edge sums can be ruled out: x=38,40,42,44,46. (x cannot be 36 because a+b+c+d=17) The amount of analysis for each of these cases, given that {a,b,c,d} is now to be chosen from {4,6,8,10,12,14,16,18,20,22,24,26,28} is not a pleasant thought.
How disappointing! 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #14 on: Jan 30th, 2005, 12:21pm » |
Quote Modify
|
Quote:| This means that none of the possible edge sums can be ruled out: x=38,40,42,44,46. |
|
If all of {a,b,c,d} are even (or two are odd and two even), then so is a + b + c + d
So, as before, we can eliminate
x = 40, a + b + c + d = 47
and
x = 44, a + b + c + d = 77
leaving
x = 38, a + b + c + d = 32
or
x = 42, a + b + c + d = 62
or
x = 46, a + b + c + d = 92
And, considering the all-even case (probably the easier one), it is not hard to see that the only way to choose four numbers that sum to 32 from {4,6,8,10,12,14,16,18,20,22,24,26,28}
is
{4,6,8,14}
and
{4,6,10,12}
FWIW,
let c be the number at the central node
let e1,e2,e3 be the three even numbers that are flanked by a,b,c,d
Then, for x = 38, 42, and 46, summing the three sides containing a,b,c,d gives
2c + e1 + e2 + e3 = 82 and 62 and 46, respectively.
In the third case we have
c + d + e1 = 46 = 2c + e1 + e2 + e3
giving
d = c + e2 + e3
But this doesn't seem to help much.
|
| « Last Edit: Jan 31st, 2005, 2:54am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Magic Hexagon
« Reply #15 on: Jan 31st, 2005, 7:58am » |
Quote Modify
|
Yea there is a solution. Like I mentioned, I was more interested in finding a method "like solving some equations" or something to just immediately come to a conclusion of number placement. Maybe first approach is to brute force it and find the solution and then maybe think what method would fit the solution to solve it (I guess)!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Magic Hexagon
« Reply #16 on: Jan 31st, 2005, 8:41am » |
Quote Modify
|
I certainly wouldn't want to brutely force 28 numbers into place..
Even if you take primes and non-primes seperately, 9!*19! is still a bit much for a computer to muddle through. Cleverly using symmetry, dividing the number of combinations by 8, still doesn't help much either.
With the work Thud's done in his first post though, I think it's tractable. After choosing a,b,c and the 9 primes, you don't need to pick d or the other 15 numbers (as you can derive them from the total you must get on each line, and d from the total of a+b+c+d)
So that leaves about 6 * 28 * 27 * 26 * 9! combinations (disregarding symmetry), which is doable.
And you can still eliminate more as we've seen.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Magic Hexagon
« Reply #17 on: Jan 31st, 2005, 5:21pm » |
Quote Modify
|
When this problem was first posted I quickly tried brute force and my program did not find a solution, so I quit. It only took a few seconds to check on a slow computer, so there are not really that many possibilites. Just cycle through each possible total, I mindlessly tried 8 through 79. Then try the 80,000 or so ways to arrange the primes. The values between primes are easily found from the total of each edge. Then it is pretty easy to check the possiblites for the remaining vertices.
Maybe the program has an error, but it was able to find a solution when all the primes are on the white spots.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #18 on: Feb 1st, 2005, 2:21am » |
Quote Modify
|
on Jan 31st, 2005, 8:41am, towr wrote:
So that leaves about 6 * 28 * 27 * 26 * 9! combinations (disregarding symmetry |
|
As the diagram is symmetrical, WLOG we can place the '2' on one of the red nodes that are connected to only one other red node. There are then 8! ways to arrange the other primes. Having placed the primes, there are 19!/16! ordered ways to choose a,b,c and 3 ways to choose d.
Hence an upper bound is merely 3*8!19!/16! = 703261440
|
| « Last Edit: Feb 1st, 2005, 3:30am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Magic Hexagon
« Reply #19 on: Feb 1st, 2005, 2:39am » |
Quote Modify
|
on Feb 1st, 2005, 2:21am, THUDandBLUNDER wrote:| As the diagram is symmetrical, WLOG we can place the '2' on one of the red nodes that are connected to only one other red node. |
|
Why not a red node connected to two other red nodes?
There are enough odds left to make that possible.
And I still don't get why not an odd number of a,b,c,d can be odd. Why must the sum be even?
|
| « Last Edit: Feb 1st, 2005, 2:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #20 on: Feb 1st, 2005, 4:23am » |
Quote Modify
|
on Feb 1st, 2005, 2:39am, towr wrote:
Why not a red node connected to two other red nodes?
|
|
You are right - the conclusion that '2' could not be between two red nodes was based upon the mistaken idea that a,b,c,d must all be odd. So the upper bound should be 6*8!19!/16! = 1406522880
Quote:| And I still don't get why not an odd number of a,b,c,d can be odd. Why must the sum be even? |
|
Merely by inspection.
Obviously, there can't be only 1 odd in {a,b,c,d} because x is even.
And if there are 3 odds there aren't enough odds to fill in the rest of the white nodes.
|
| « Last Edit: Feb 1st, 2005, 6:09am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Magic Hexagon
« Reply #21 on: Feb 1st, 2005, 4:49am » |
Quote Modify
|
on Feb 1st, 2005, 4:23am, THUDandBLUNDER wrote:Merely by inspection.
Obviously, there can't be only 1 odd in {a,b,c,d} because x is even. |
|
If, say, c is odd and b is even, the number in between can still be odd, which gives an even x.
|
| « Last Edit: Feb 1st, 2005, 4:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #22 on: Feb 1st, 2005, 6:02am » |
Quote Modify
|
Quote:| If, say, c is odd and b is even, the number in between can still be odd, which gives an even x. |
|
Well, duh! 
I should have taken more notice of Sameer's sig.
However, you have now used 4 of your 6 odds.
And there's no getting away from the fact that x is even.
So where are you going to put the other 2?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Magic Hexagon
« Reply #23 on: Feb 1st, 2005, 7:00am » |
Quote Modify
|
You can vary the number of odds you can play with by positioning the 2.
It must be flanked by either one or two odds, depending on wether it is connected to one or two other primes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Magic Hexagon
« Reply #24 on: Feb 1st, 2005, 7:42am » |
Quote Modify
|
on Feb 1st, 2005, 7:00am, towr wrote:You can vary the number of odds you can play with by positioning the 2.
It must be flanked by either one or two odds, depending on wether it is connected to one or two other primes. |
|
There are 5 free odds if the '2' is positioned so as to connect to only one other red node.
Otherwise, there are only 4 free odds.
Can you find a configuraton of the 19 non-primes such that a + b + c + d is odd?
|
| « Last Edit: Feb 1st, 2005, 7:09pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove