2005 USAMO Problems/Problem 1
Problem
(Zuming Feng) 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
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.
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 .
Solution 2
The proof that no arrangement exists for , where are distinct primes follows from above. Apply induction to prove all other cases are possible
Base case:
- , where is a prime and is a positive integer. Any arrangement suffices
- , where are distinct primes. The following configuration works
Inductive step: Suppose the desired arrangement exists for a composite , show the arrangement exists for , where is a prime relatively prime to and is a positive integer
Let be the arrangement of divisors of , then for , where . The divisors of greater than 1 are of the form The following sequence works since all other divisors are divisible by .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=34314 Discussion on AoPS/MathLinks</url>
2005 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.