2005 USAMO Problems/Problem 1

Problem

Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

Solution

First, we can note that if $n$ is a multiple of two distinct primes, then an arrangement isn't possible. We use the canonical factorization of $n$ , which is $p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . In this, we have $k > 2$ , or it'll be messed. So now we can arrange a circle with $n$ being on the top, and then having factors $p_1p_2$ , $p_2p_3$ , and so on complete around the circle until we reach the other side of the circle where the number would be $p_{k - 1}p_k$ .

We create $S$ such that in $S_n$ , $s: s|n; s > 1$ .

We may have an element WOLOG between $p_1p_2$ and $p_2p_3$ (or any other respective number likewise). We interject the member of $D$ which has the smallest prime factor smaller than the smallest prime factor of $p_2p_3$ and larger than the smallest prime factor of $p_1p_2$ . Now, all of the elements in $D$ have been placed in the circle.

The restrictions are met, and we are done. $\Box$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

2005 USAMO (Problems • Resources)
Preceded by First question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2005 USAMO Problems/Problem 1

Problem

Solution

Resources