Difference between revisions of "2005 USAMO Problems/Problem 1"
I like pie (talk | contribs) (Official solution (image needed)) |
I like pie (talk | contribs) (Dscussion on forum, alternate solutions, author) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Determine all composite positive integers <math>n</math> for which it is possible to arrange all divisors of <math>n</math> that are greater than 1 in a circle so that no two adjacent divisors are relatively prime. | + | (''Zuming Feng'') Determine all composite positive integers <math>n</math> for which it is possible to arrange all divisors of <math>n</math> that are greater than 1 in a circle so that no two adjacent divisors are relatively prime. |
== Solution == | == Solution == | ||
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>. | ''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>. | ||
+ | |||
+ | {{alternate solutions}} | ||
== See also == | == See also == | ||
+ | * <url>viewtopic.php?t=34314 Discussion on AoPS/MathLinks</url> | ||
+ | |||
{{USAMO newbox|year=2005|before=First Question|num-a=2}} | {{USAMO newbox|year=2005|before=First Question|num-a=2}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 12:24, 3 May 2008
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.
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 .
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 |