1990 USAMO Problems/Problem 3

Revision as of 18:14, 18 July 2016 by 1=2 (talk | contribs) (Resources)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

See Also

1990 USAMO (ProblemsResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS