Difference between revisions of "2005 USAMO Problems/Problem 1"
I like pie (talk | contribs) m |
I like pie (talk | contribs) (Official solution (image needed)) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | === Solution 1 (official solution) === |
| + | No such circular arrangement exists for <math>n=pq</math>, where <math>p</math> and <math>q</math> are distinct primes. In that case, the numbers to be arranged are <math>p</math>; <math>q</math> and <math>pq</math>, and in any circular arrangement, <math>p</math> and <math>q</math> will be adjacent. We claim that the desired circular arrangement exists in all other cases. If <math>n=p^e</math> where <math>e\ge2</math>, an arbitrary circular arrangement works. Henceforth we assume that <math>n</math> has prime factorization <math>p^{e_1}_{1}p^{e_2}_{2}\cdots p^{e_k}_k</math>, where <math>p_1<p_2<\cdots<p_k</math> and either <math>k>2</math> or else <math>\max(e1,e2)>1</math>. To construct the desired circular arrangement of <math>D_n:=\lbrace d:d|n\ \text{and}\ d>1\rbrace</math>, start with the circular arrangement of <math>n,p_{1}p_{2},p_{2}p_{3}\ldots,p_{k-1}p_{k}</math> as shown. | ||
| + | |||
| + | {{image}} | ||
| + | |||
| + | Then between <math>n</math> and <math>p_{1}p_{2}</math>, place (in arbitrary order) all other members of <math>D_n</math> that have <math>p_1</math> as their smallest prime factor. Between <math>p_{1}p_{2}</math> and <math>p_{2}p_{3}</math>, place all members of <math>D_n</math> other than <math>p_{2}p_{3}</math> that have <math>p_2</math> as their smallest prime factor. Continue in this way, ending by placing <math>p_k,p^{2}_{k},\ldots,p^{e_k}_{k}</math> between <math>p_{k-1}p_k</math> and <math>n</math>. It is easy to see that each element of <math>D_n</math> 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 <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>. | ||
== See also == | == See also == | ||
Revision as of 12:21, 3 May 2008
Problem
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.
An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.
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 
.
See also
| 2005 USAMO (Problems • Resources) | ||
| Preceded by First Question |
Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
