With pearls of different colours form necklaces, it is said that a necklace is prime if it cannot be decomposed into strings of pearls of the same length, and equal to each other. Let $n$ and $q$ be positive integers. Prove that the number of prime necklaces with $n$ beads, each of which has one of the $q^n$ possible colours, is equal to $n$ times the number of prime necklaces with $n^2$ pearls, each of which has one of $q$ possible colours. Note: two necklaces are considered equal if they have the same number of pearls and you can get the same colour on both necklaces, rotating one of them to match it to the other.
Problem
Source: CentroAmerican 2004
Tags: combinatorics proposed, combinatorics
MexicOMM
31.12.2013 08:17
Actually you wrote wrong this problem, it is not "if it can be descomposed..." but "if it can NOT be descomposed...".
theflowerking
23.06.2015 05:04
(Notice that being prime equals being unable to rotate the necklace and still it being identical. If a non-prime necklace can be rotated by $d$ pearls and be identical, then I say it has period $d$). There is a function $ f: A \rightarrow B$ where $A$ is the set of $n$-pearled, $q^n$-colored prime necklaces and $B$ the number of $n^2$-pearled, $q$-colored prime necklaces. This function satisfies that for all $ b \in B $ there are exactly $ n $ elements $ a \in A$ with $ f(a)=b $ (this finishes the problem). To explain the function, take any necklace in $A$, and consider the colors as numbers with $n$ digits base $n$. Each pearl will be replaced by $n$ pearls (in order), each colored with the respective digit. Hence we use $q$ colors (the digits) and $n^2$ pearls. To see the resulting necklace is prime, assume it is not. Then it has period $d | n^2$, $d<n^2$. So assume $d=ab$ with $a,b | n$. It is easy to see that the old necklace has period $[d,n]/n$. Hence, $[d,n]=n^2$. But $[d,n] | an$ so $a=n$ and similarly $b=n$. So $d=n^2$, contradiction. To see that for each element in $b$ there are $n$ elements $a$ in $A$ such that $f(a)=b$, simply note that there are $n$ ways to group together blocks of $n$ consecutive pearls of $b$.