Problem:
Determine all composite positive integers for which it is possible to arrange all divisors of that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.
Solution:
No such circular arrangement exists for , where and are distinct primes. In that case, the numbers to be arranged are and , and in any circular arrangement, and will be adjacent. We claim that the desired circular arrangement exists in all other cases. If where , an arbitrary circular arrangement works. Henceforth we assume that has prime factorization , where and either or else . To construct the desired circular arrangement of , start with the circular arrangement of as shown.
Then between and , place (in arbitrary order) all other members of that have as their smallest prime factor. Between and , place all members of other than that have as their smallest prime factor. Continue in this way, ending by placing between and . It is easy to see that each element of is placed exactly one time, and any two adjacent elements have a common prime factor. Hence this arrangement has the desired property.
Note. In graph theory terms, this construction yields a Hamiltonian cycle in the graph with vertex set in which two vertices form an edge if the two corresponding numbers have a common prime factor. The graphs below illustrate the construction for the special cases and .
This problem was proposed by Zuming Feng.
cycle of length in a graph is a sequence of distinct vertices such that
are edges. A cycle that uses every vertex of the graph is a Hamiltonian cycle.
The problems on this page are the property of the MAA's American Mathematics Competitions