For every integer $n \ge 2$ let $B_n$ denote the set of all binary $n$-nuples of zeroes and ones, and split $B_n$ into equivalence classes by letting two $n$-nuples be equivalent if one is obtained from the another by a cyclic permutation.(for example 110, 011 and 101 are equivalent). Determine the integers $n \ge 2$ for which $B_n$ splits into an odd number of equivalence classes.
Problem
Source: Romania 2018 TST Problem 3 Day 3
Tags: Binary, combinatorics, permutation
26.05.2020 03:41
secretly a bad nt problem The only such $n$ is $n = 2$. Let $S = \sum_{d \mid n}\varphi(\tfrac{n}{d})2^d$. By Burnside's Lemma, the number of orbits $B_n$ is partitioned into is $$\frac{1}{n}\sum_{i = 0}^{n-1} 2^{\gcd(i, n)} = \frac{1}{n}\sum_{d \mid n}\varphi(\tfrac{n}{d})2^d = \frac{S}{n}.$$ Claim: $v_2(S) \geq v_2\left(\varphi(n)\right)+1$. Proof: It suffices to check that $v_2\left(\varphi(\tfrac{n}{d})\right) + d \geq v_2\left(\varphi(n)\right) + 1$ for all $d>1$, and this should seem obvious because $d$ should increase more than $v_2\left(\varphi(\tfrac{n}{d})\right)$ decreases. Consider the bound $$v_2\left(\varphi(\tfrac{n}{d})\right) + v_2\left(\varphi(d) \right) = v_2\left(\varphi(\tfrac{n}{d})\varphi(d)\right) \geq v_2\left(\varphi(n)\right) - 1,$$which follows by observing individual prime powers dividing $\tfrac{n}{d}$ and $d$. Then we have \begin{align*} v_2\left(\varphi(\tfrac{n}{d})\right) + d &\geq v_2\left(\varphi(n)\right) + 1 + d - v_2\left(\varphi(d)\right) - 2 \\ &\geq v_2\left(\varphi(n)\right) + 1 \end{align*}because $d - v_2\left(\varphi(d)\right) - 2 = 0$ for $d = 2, 3$ and $d \geq \log_2(d) + 2 \geq v_2\left(\varphi(d)\right) + 2$ for $d \geq 4$. This proves the claim. $\blacksquare$ This claim is important because it implies $v_2\left(S\right) \geq v_2\left(\varphi(n)\right) + 1 \geq v_2\left(n\right)$ -- this is because $\varphi$ can only knock off one $2$ from $n$, but every odd prime dividing $n$ contributes to $ v_2\left(\varphi(n)\right)$. In particular, if the inequality is strict, then the number of orbits $\tfrac{S}{n}$ is even. Thus we must have equality in both inequalities, i.e. $n$ is a power of $2$ and $n \in \{2, 3, 4\}$. Manually checking, $B_2$ has $3$ orbits, and $n = 2$ is the only $n$ that works.