0
$\begingroup$

Suppose we want to prove the following simple statement rigorously -

If the number of beads in a necklace is $n$ then there exists a colored (suppose we have infinitely many colors at our disposal) necklace of minimal period $k$ (rotations) iff $k|n$.

Intuitively this seems obvious, but how do you make a rigorous proof?

EDIT : I think i figured this one : given that for some string of length $n$, $k$ is the minimal period, use the euclidean algorithm to get $n=qk+r$, $0\leq r<k$. Then it is easy to see that the string is also $r$-periodic (because it is $n$-periodic & $qk$-periodic). So $r=0$ because $k$ is minimal. The other direction of the proof is quite easy - just break up the string into chunks of $k$ beads, color every bead differently and repeat for all chunks.

$\endgroup$
4
  • 1
    $\begingroup$ Make a period with $k-1$ red and $1$ blue, what's the problem ? $\endgroup$
    – user65203
    Jun 29 '20 at 20:31
  • $\begingroup$ @YvesDaoust The other direction of the double-implication. $\endgroup$
    – hello_123
    Jun 29 '20 at 20:37
  • $\begingroup$ How do you define the period if $k\not|n$ ? $\endgroup$
    – user65203
    Jun 29 '20 at 21:18
  • $\begingroup$ @YvesDaoust $\forall i$ Color(Bead$_{i}$) = Color(Bead$_{i+k}$) $\endgroup$
    – hello_123
    Jun 29 '20 at 21:24
0
$\begingroup$

If $k\not|n$ and the period is $k$, then take every other $k^{th}$ beads. After several turns, you will get $\dfrac n{\gcd(k,n)}$ different positions, spaced by $\dfrac{k}{\gcd(k,n)}$, holding beads of the same color. Hence the period is $\gcd(k,n)<k$, a contradiction.

E.g. $k=6,n=15\to\gcd(k,n)=3$.

The beads $0,6,12,3,9$ ($5$ of them) have the same color; also $1,7,13,4,10$ and $2,8,14,5,11$. Hence $0,1,2$ is a period !?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.