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
.
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 |