2005 USAMO Problems/Problem 1: Difference between revisions

Revision as of 21:30, 14 April 2008

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

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

@@ Line 4: / Line 4: @@
 == Solution ==
-First, we can note that if <math>n</math> is a multiple of two distinct primes, then an arrangement isn't possible. We use the canonical factorization of <math>n</math>, which is <math>p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}</math>. In this, we have <math>k > 2</math>, or it'll be messed. So now we can arrange a circle with <math>n</math> being on the top, and then having factors <math>p_1p_2</math>, <math>p_2p_3</math>, and so on complete around the circle until we reach the other side of the circle where the number would be <math>p_{k - 1}p_k</math>.
-We create <math>S</math> such that in <math>S_n</math>, <math>s: s|n; s > 1</math>.
-We may have an element WOLOG between <math>p_1p_2</math> and <math>p_2p_3</math> (or any other respective number likewise). We interject the member of <math>D</math> which has the smallest prime factor smaller than the smallest prime factor of <math>p_2p_3</math> and larger than the smallest prime factor of <math>p_1p_2</math>. Now, all of the elements in <math>D</math> have been placed in the circle.
-The restrictions are met, and we are done. <math>\Box</math>

Page

Toolbox

Search

2005 USAMO Problems/Problem 1: Difference between revisions

Revision as of 21:30, 14 April 2008

Problem

Solution

Resources