D. S_D23

Contributed by Christopher Bistryski, Eagle Problem Solvers, Blazej Kot, Robert Noll, and Christopher West, Monroe, WA, Georgia Southern University, PMP, PMP, and PMP

One elegant way to find an acceptable numbering is to assign every edge a different prime number, and then label each vertex by the product of the prime numbers assigned to all of the edges leaving it. Whatever primes you choose, that labeling satisfies all of the desired properties.

However, it doesn’t in general produce the smallest solution. For that, you need an argument more specifically tailored to this particular network. If any vertex of the octahedron is labeled by a prime (or a power of a prime), then the four adjacent vertices must be labeled with multiples of this prime. But that labeling would violate the rules, because two of those four adjacent vertices are not connected, yet their labels have a common factor of that prime.

Therefore, each vertex must be labeled with a number that has at least two distinct prime factors. Since opposite vertices cannot share a prime factor, at least four primes must occur as factors of labels. Moreover, opposite vertices must have different labels, and adjacent vertices must also have different labels because the vertex opposite the first of an adjacent pair is adjacent to the second. Therefore, the labeling with smallest possible sum would involve the six possible products of pairs of the four smallest primes. And indeed, there is such a solution: label pairs of opposite vertices 6 and 35, 10 and 21, and 14 and 15, in any order. Thus, the minimum possible sum is 6 + 10 + 14 + 15 + 21 + 35 = 101 .

This problem originally appeared in the Prisoner’s Dilemma in the issue of the PMP Newsletter. Solutions will be accepted through .