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 13: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 |