MathDB
Beaded necklaces

Source: USAMO 1990

October 27, 2005
modular arithmeticnumber theorygreatest common divisorrelatively primecombinatorics unsolvedcombinatorics

Problem Statement

Suppose that necklace  A \, A \, has 14 beads and necklace  B \, B \, has 19. Prove that for any odd integer n≥1n \geq 1, there is a way to number each of the 33 beads with an integer from the sequence {n,n+1,n+2,…,n+32} \{ 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.)
Back to ProblemsView on AoPS