1990 USAMO Problems/Problem 3
Problem
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.)
Solution
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.
Resources
1990 USAMO (Problems • Resources) | ||
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.