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

       A
       |
    B--C--D
      / \
     E   F
      \
  G   H
   \ /
 I--J--K
    |
    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 vis-a-vis 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 A-Z

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 A-Z
SUB permute (a$)
DEFINT A-Z
 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 2007-06-01 17:51:00