Very roughly this is the net of a dodecahedron; each letter represents a pentagon.
A

BCD
/ \
E F
\
G H
\ /
IJK

L
Consider each face to be numbered 1 through 12.
Each vertex is the intersection of 3 faces. The vertex sum is therefore the sum of the values of those three faces.
The faces making up the vertices in the diagram above are:
1. ABC 2. ABI 3. ACD 4. ADL 5. AIL
6. BCE 7. BEG 8. BGI 9. CDF 10. CEF
11. DKF 12. DKL 13. EFH 14. EGH 15. FHK
16. GHJ 17. GIJ 18. HJK 19. IJL 20. JKL.
What is the global vertex sum (20 vertices) and therefore the mean vertex sum?
How best can the faces be labeled so that the 20 vertices are as close as possible to the mean vertex sum?
“Close as possible” means that:
the sum of differences above (or below) the mean is at the optimum
or
the most vertex sums land on or have the best proximity to the mean as possible. The prior condition also applies; ie, any deviance is minimal.
In writing the program to find a best solution, we want to visit as few possible permutations of numbers vs. letters. Without loss of generality we can say that the 1 is taken to be on face C, which conceptually I place in the center of the top half of the dodecahedron. Then we have to choose 5 of the remaining 11 (without regard to order, so it the selection is done in ascending order). Also without loss of generality, the lowest of these can be placed on face E, and we can always make sure the number on F is lower than the number on B; other than that all permutations of the digits for F, D, A and B can be used.
Then every permutation of the remaining numbers visavis the remaining letters G thru L need be tried.
As a result, under 4 million combinations need be tried, which is considerably less than 12!.
DECLARE SUB permute (a$)
DEFDBL AZ
DIM taken(12)
CLS
avg = 19.5
tdMax = 9999999
tsqMax = 99999999999#
c = 1
FOR v1 = 2 TO 8: taken(v1) = 1
FOR v2 = v1 + 1 TO 9: taken(v2) = 1
FOR v3 = v2 + 1 TO 10: taken(v3) = 1
PRINT v1; v2; v3
FOR v4 = v3 + 1 TO 11: taken(v4) = 1
FOR v5 = v4 + 1 TO 12: taken(v5) = 1
s1$ = CHR$(v2) + CHR$(v3) + CHR$(v4) + CHR$(v5)
h1$ = s1$
DO
IF LEFT$(s1$, 1) < RIGHT$(s1$, 1) THEN
e = v1
f = ASC(LEFT$(s1$, 1))
d = ASC(MID$(s1$, 2, 1))
a = ASC(MID$(s1$, 3, 1))
b = ASC(MID$(s1$, 4, 1))
s2$ = ""
FOR ii = 2 TO 12
IF taken(ii) = 0 THEN
s2$ = s2$ + CHR$(ii)
END IF
NEXT ii
h2$ = s2$
DO
h = ASC(LEFT$(s2$, 1))
k = ASC(MID$(s2$, 2, 1))
l = ASC(MID$(s2$, 3, 1))
i = ASC(MID$(s2$, 4, 1))
g = ASC(MID$(s2$, 5, 1))
j = ASC(MID$(s2$, 6, 1))
td = 0: tsq = 0
diff = ABS(a + b + c  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(a + b + i  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(a + c + d  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(a + d + l  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(a + i + l  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(b + c + e  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(b + e + g  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(b + g + i  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(c + d + f  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(c + e + f  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(d + k + f  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(d + k + l  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(e + f + h  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(e + g + h  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(f + h + k  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(g + h + j  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(g + i + j  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(h + j + k  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(i + j + l  avg): td = td + diff: tsq = tsq + diff * diff
diff = ABS(j + k + l  avg): td = td + diff: tsq = tsq + diff * diff
IF td < tdMax THEN
tdMax = td
PRINT a; b; c; d; e; f; g; h; i; j; k; l, td / 20
PRINT (a + b + c  avg);
PRINT (a + b + i  avg);
PRINT (a + c + d  avg);
PRINT (a + d + l  avg);
PRINT (a + i + l  avg);
PRINT (b + c + e  avg);
PRINT (b + e + g  avg);
PRINT (b + g + i  avg);
PRINT (c + d + f  avg);
PRINT (c + e + f  avg);
PRINT (d + k + f  avg);
PRINT (d + k + l  avg);
PRINT (e + f + h  avg);
PRINT (e + g + h  avg);
PRINT (f + h + k  avg);
PRINT (g + h + j  avg);
PRINT (g + i + j  avg);
PRINT (h + j + k  avg);
PRINT (i + j + l  avg);
PRINT (j + k + l  avg)
END IF
IF tsq < tsqMax THEN
tsqMax = tsq
PRINT a; b; c; d; e; f; g; h; i; j; k; l, SQR(tsq / 20); " (sq)"
PRINT (a + b + c  avg);
PRINT (a + b + i  avg);
PRINT (a + c + d  avg);
PRINT (a + d + l  avg);
PRINT (a + i + l  avg);
PRINT (b + c + e  avg);
PRINT (b + e + g  avg);
PRINT (b + g + i  avg);
PRINT (c + d + f  avg);
PRINT (c + e + f  avg);
PRINT (d + k + f  avg);
PRINT (d + k + l  avg);
PRINT (e + f + h  avg);
PRINT (e + g + h  avg);
PRINT (f + h + k  avg);
PRINT (g + h + j  avg);
PRINT (g + i + j  avg);
PRINT (h + j + k  avg);
PRINT (i + j + l  avg);
PRINT (j + k + l  avg)
END IF
permute s2$
LOOP UNTIL s2$ = h2$
END IF
permute s1$
LOOP UNTIL h1$ = s1$
taken(v5) = 0
NEXT
taken(v4) = 0
NEXT
taken(v3) = 0
NEXT
taken(v2) = 0
NEXT
taken(v1) = 0
NEXT
DEFSNG AZ
SUB permute (a$)
DEFINT AZ
x$ = ""
FOR i = LEN(a$) TO 1 STEP 1
l$ = x$
x$ = MID$(a$, i, 1)
IF x$ < l$ THEN EXIT FOR
NEXT
IF i = 0 THEN
FOR j = 1 TO LEN(a$) \ 2
x$ = MID$(a$, j, 1)
MID$(a$, j, 1) = MID$(a$, LEN(a$)  j + 1, 1)
MID$(a$, LEN(a$)  j + 1, 1) = x$
NEXT
ELSE
FOR j = LEN(a$) TO i + 1 STEP 1
IF MID$(a$, j, 1) > x$ THEN EXIT FOR
NEXT
MID$(a$, i, 1) = MID$(a$, j, 1)
MID$(a$, j, 1) = x$
FOR j = 1 TO (LEN(a$)  i) \ 2
x$ = MID$(a$, i + j, 1)
MID$(a$, i + j, 1) = MID$(a$, LEN(a$)  j + 1, 1)
MID$(a$, LEN(a$)  j + 1, 1) = x$
NEXT
END IF
END SUB
The optimum assignments found are
A B C D E F G H I J K L Avg deviation
8 11 1 10 7 9 6 4 2 12 3 5 1.7
The individual deviations of the vertices are
.5 1.5 .5 3.5 4.5 .5 4.5 .5 .5 2.5 2.5 1.5 .5 2.5 3.5 2.5 .5 .5 .5 .5
So 1.7 is the smallest average deviation from the mean that you can get.
I thought it would be instructive to see what would happen if we sought to minimize the average square of the deviations from the mean, rather than the average absolute value. Indeed a different set of assignments results in optimum there:
A B C D E F G H I J K L Avg squared deviation
8 11 1 9 7 10 4 5 3 12 2 6 1.962141687034858
and the individual deviations themselves (not squares) are
.5 2.5 1.5 3.5 2.5 .5 2.5 1.5 .5 1.5 1.5 2.5 2.5 3.5 2.5 1.5 .5 .5 1.5 .5
showing less extreme deviations (both small and large).

Posted by Charlie
on 20070601 17:51:00 