wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes Magic Caterpillar Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Magic Caterpillar" Watch "Magic Caterpillar" New topic
Author

Magic Caterpillar

Lu Battist
Ranch Hand

Joined: Feb 17, 2003
Posts: 104
I found this problem from http://nrich.maths.org/mathsf/journalf/feb03/stage4new.html
The problem is that you have 6 vertices connected by 5 edges in the following way:
0---0
/ \ / \
0 0 0 0
The integers 1 through 11 are to be assigned to each vertex and each edge in such a way that the vertex sum is the same number for each vertex. A vertex sum is the sum of the vertex and each edge connected to that vertex. For example if I had a vertex with value 1 and 3 edges with values (8,9,and 7) then the vertex sum would be 25. If I had another vertex with value 2 and 1 edge with value 8 that would have a sum of 10.
The challenge is write a program to print all the solutions to this problem. Just finding a solution is pretty fun.
[ June 05, 2003: Message edited by: Lu Battist ]
Roy Tock
Ranch Hand

Joined: Jul 16, 2001
Posts: 83
SPOILER - SPOILER - SPOILER
There's only one real solution; the other seven are reflections of various sorts. I prefer reasoning these out to brute force, if possible.
First... Note that all the vertices are counted once, and the edges are counted twice (once for each vertex endpoint). So the LEAST that the total vertex sum could be is 2(1+2+3+4+5)+6+7+8+9+10+11=81, and the MOST that the total vertex sum could be is 1+2+3+4+5+6+2(7+8+9+10+11)=111. Since there are 6 vertices, the total vertex sum must be divisible by 6. Thus it must be one of 84, 90, 96, 102, or 108.
Assume it's 108; then each of the vertex sums must be 18, so each of the 4 feet (one vertex plus edge) must sum to 18. Thus we have to have four different ways to sum to 18. 11+7 is 18 and 10+8 is 18, but that's all we've got. So the total sum can't be 108.
Similarly, we can eliminate 102=6*17 since we only have enough sums for three legs (11+6, 10+7, and 9+8). We can also eliminate 96=6*16 since we only have enough sums for three legs (11+5, 10+6, and 9+7).
Assume the sum is 84. Then each vertex adds to 14=11+3=10+4=9+5=8+6, which takes care of the four feet and legs. The numbers left are 1, 2, and 7. If we put 7 in one of the top vertices, the vertex will end up summing too high, because the least connecting legs would have 3 and 4. If we put 7 in the caterpillar's back, both top vertices will sum too high for the same reason. So the sum can't be 84.
That leaves us with 90. Then each vertex adds to 15=11+4=10+5=9+6=8+7, which takes care of the four feet and legs. The numbers left are 1, 2, and 3. A little jostling numbers around leads us to the one and only solution (up to reflections of various sorts), which I won't state here because it'll take the fun out of it for the rest of y'all.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Magic Caterpillar