Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 USAMO Problems/Problem 3"

(problem and solution)
 
(category change)
Line 30: Line 30:
  
  
−
[[Category:Olympiad Combinatorics Problems]]
+
[[Category:Olympiad Number Theory Problems]]

Revision as of 23:18, 11 January 2008

Problem

Suppose that necklace $\, A \,$ has 14 beads and necklace $\, B \,$ has 19. Prove that for any odd integer $n \geq 1$, there is a way to number each of the 33 beads with an integer from the sequence \[\{ n, n+1, n+2, \dots, n+32 \}\] so that each integer is used once, and adjacent beads correspond to relatively prime integers. (Here a "necklace" is viewed as a circle in which each bead is adjacent to two other beads.)

Solution

Lemma. For every positive odd integer $n$, there exists a nonnegative integer $k \le 17$ such that $n+k$ is relatively prime to $n+k+15$, $n+k+1$ is relatively prime to $n+k+14$.

Proof. Consider the positive integers $n, n+1, n+2$. Note that at most one of these is divisible by 3, and at most one is divisible by 5. Therefore one of these, say $n+a$, is divisible by neither, and is therefore relatively prime to 15. Furthermore, $n+a+1$ and $n+(a+15)+1$ have different residues mod 13, so one of them, say $n+b+1$, is relatively prime to 13. Since $n+b \equiv n+a \pmod{15}$, $n+b$ is relatively prime to 15. But \[\gcd(n+b,n+b+15) = \gcd\bigl[ n+b,(n+b+15) - (n+b) \bigr] = \gcd(n+b,15) = 1,\] so $n+b$ is relatively prime to $n+b+15$. Also, \[\gcd(n+b+1, n+b+14) = \gcd \bigl[ n+b+1, (n+b+14)-(n+b+1) \bigr] = \gcd( n+b+1, 13) ,\] so $n+b+1$ is relatively prime to $n+b+14$. Finally, $b \le a+15 \le 17$. It follows that setting $k=b$ satisfies the lemma. $\blacksquare$

Let $k$ be an integer as described in the lemma. We place the integers $n, \dotsc, n+k, n+k+15, \dotsc, n+32$ on the necklace with 19 beads, and the integers $n+k+1, \dotsc, n+k+14$ on the necklace with 14 beads, in those orders. Since $n$ is odd, $n$ is relatively prime to $n+32 = n+2^5$. By definition, $n+k$ and $n+k+15$ are relatively prime, as are $n+k+1$ and $n+k+14$; finally, $a$ and $a+1$ are relatively prime for all integers $a$. It follows that each bead in this arrangement is relatively prime to its neighbors. $\blacksquare$


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

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_3&oldid=22358"