Lu Battist

Ranch Hand

Posts: 104

posted 14 years ago

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 ]

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

Posts: 83

posted 14 years ago

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.

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.