Difference between revisions of "2005 USAMO Problems/Problem 1"

Revision as of 18:34, 26 August 2012

Problem

(Zuming Feng) 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

Solution 1 (official solution)

No such circular arrangement exists for $n=pq$ , where $p$ and $q$ are distinct primes. In that case, the numbers to be arranged are $p$ ; $q$ and $pq$ , and in any circular arrangement, $p$ and $q$ will be adjacent. We claim that the desired circular arrangement exists in all other cases. If $n=p^e$ where $e\ge2$ , an arbitrary circular arrangement works. Henceforth we assume that $n$ has prime factorization $p^{e_1}_{1}p^{e_2}_{2}\cdots p^{e_k}_k$ , where $p_1<p_2<\cdots<p_k$ and either $k>2$ or else $\max(e1,e2)>1$ . To construct the desired circular arrangement of $D_n:=\lbrace d:d|n\ \text{and}\ d>1\rbrace$ , start with the circular arrangement of $n,p_{1}p_{2},p_{2}p_{3}\ldots,p_{k-1}p_{k}$ as shown.

Then between $n$ and $p_{1}p_{2}$ , place (in arbitrary order) all other members of $D_n$ that have $p_1$ as their smallest prime factor. Between $p_{1}p_{2}$ and $p_{2}p_{3}$ , place all members of $D_n$ other than $p_{2}p_{3}$ that have $p_2$ as their smallest prime factor. Continue in this way, ending by placing $p_k,p^{2}_{k},\ldots,p^{e_k}_{k}$ between $p_{k-1}p_k$ and $n$ . It is easy to see that each element of $D_n$ 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 $D_n$ 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 $n=p^{2}q$ and $n=pqr$ .

Solution 2

The proof that no arrangement exists for $n=pq$ , where $p,q$ are distinct primes follows from above. Apply induction to prove all other cases are possible

Base case:

$n=p^r$ , where $p$ is a prime and $r$ is a positive integer. Any arrangement suffices
$n=pqr$ , where $p,q,r$ are distinct primes. The following configuration works

Inductive step: Suppose the desired arrangement exists for a composite $n$ , show the arrangement exists for $np^r$ , where $p$ is a prime relatively prime to $n$ and $r$ is a positive integer

Let $a_1,a_2,\cdots,a_m$ be the arrangement of divisors of $n$ , then $(a_i,a_{i+1})>1$ for $i=1,2,\cdots,m$ , where $a_{m+1}=a_1$ . The divisors of $np^r$ greater than 1 are of the form $a_ip^j,p^j\qquad 1\leq i\leq m,1\leq j\leq r$ The following sequence works $a_1,\cdots,a_{m-1}, a_{m-1}p,\text{other divisors in arbitrary order},a_mp,a_m$ since all other divisors are divisible by $p$ .

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

@@ Line 11: / Line 11: @@
 ''Note.'' In graph theory terms, this construction yields a Hamiltonian cycle in the graph with vertex set <math>D_n</math> 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 <math>n=p^{2}q</math> and <math>n=pqr</math>.
+=== Solution 2 ===
+The proof that no arrangement exists for <math>n=pq</math>, where <math>p,q</math> are distinct primes follows from above. Apply induction to prove all other cases are possible
+Base case:
+#<math>n=p^r</math>, where <math>p</math> is a prime and <math>r</math> is a positive integer. Any arrangement suffices
+#<math>n=pqr</math>, where <math>p,q,r</math> are distinct primes. The following configuration works
+Inductive step: Suppose the desired arrangement exists for a composite <math>n</math>, show the arrangement exists for <math>np^r</math>, where <math>p</math> is a prime relatively prime to <math>n</math> and <math>r</math> is a positive integer
+Let <math>a_1,a_2,\cdots,a_m</math> be the arrangement of divisors of <math>n</math>, then <math>(a_i,a_{i+1})>1</math> for <math>i=1,2,\cdots,m</math>, where <math>a_{m+1}=a_1</math>. The divisors of <math>np^r</math> greater than 1 are of the form
+<cmath>a_ip^j,p^j\qquad 1\leq i\leq m,1\leq j\leq r</cmath>
+The following sequence works
+<cmath>a_1,\cdots,a_{m-1}, a_{m-1}p,\text{other divisors in arbitrary order},a_mp,a_m</cmath>
+since all other divisors are divisible by <math>p</math>.
 {{alternate solutions}}

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