2005 USAMO Problems/Problem 1
From AoPSWiki
Contents |
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 
.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
| 2005 USAMO (Problems) | ||
| Preceded by First Question | 1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
