2005 USAMO Problems/Problem 1
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 1 (official 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.
An image is supposed to go here. You can help us out by creating one and. Thanks.
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 .
|2005 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|