1990 USAMO Problems/Problem 3

From AoPSWiki

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$