VN-TST 2016 Problem 5

Given $n$ numbers $a_1,a_2,...,a_n$ ( $n\geq 3$ ) where $a_i\in\{0,1\}$ for all $i=1,2.,,,.n$ . Consider $n$ following $n$ -tuples $$\begin{aligned} S_1 & =(a_1,a_2,...,a_{n-1},a_n) S_2 & =(a_2,a_3,...,a_n,a_1) & \vdots S_n & =(a_n,a_1,...,a_{n-2},a_{n-1}).\end{aligned}$$ For each tuple $r=(b_1,b_2,...,b_n)$ , let $$\omega (r)=b_1\cdot 2^{n-1}+b_2\cdot 2^{n-2}+\cdots+b_n.$$ Assume that the numbers $\omega (S_1),\omega (S_2),...,\omega (S_n)$ receive exactly $k$ different values.

a) Prove that $k|n$ and $\frac{2^n-1}{2^k-1}|\omega (S_i) \forall i=1,2,...,n.$ b) Let $$\begin{aligned} M & =\max _{i=\overline{1,n}}\omega (S_i) m & =\min _{i=\overline{1,n}}\omega (S_i). \end{aligned}$$ Prove that $$M-m\geq\frac{(2^n-1)(2^{k-1}-1)}{2^k-1}.$$