You want to label the vertices (corners) of a regular octahedron (see Figure 3) with whole numbers bigger than one so that the labels of two vertices have a common factor (bigger than one) if and only if they are adjacent on the octahedron (connected by an edge). Is it possible? If so, what is the minimum possible sum of the labels?
This problem originally appeared in the Prisoner’s Dilemma in the 2024 Fall issue of the PMP Newsletter. Solutions are no longer being accepted for this Dilemma.
Show solution?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 .