1990 USAMO Problems/Problem 3
Suppose that necklace has 14 beads and necklace has 19. Prove that for any odd integer , there is a way to number each of the 33 beads with an integer from the sequence 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.)
Lemma. For every positive odd integer , there exists a nonnegative integer such that is relatively prime to , is relatively prime to .
Proof. Consider the positive integers . Note that at most one of these is divisible by 3, and at most one is divisible by 5. Therefore one of these, say , is divisible by neither, and is therefore relatively prime to 15. Furthermore, and have different residues mod 13, so one of them, say , is relatively prime to 13. Since , is relatively prime to 15. But so is relatively prime to . Also, so is relatively prime to . Finally, . It follows that setting satisfies the lemma.
Let be an integer as described in the lemma. We place the integers on the necklace with 19 beads, and the integers on the necklace with 14 beads, in those orders. Since is odd, is relatively prime to . By definition, and are relatively prime, as are and ; finally, and are relatively prime for all integers . It follows that each bead in this arrangement is relatively prime to its neighbors.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|1990 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|