Problem

Source: Vietnam TST 2016 - P5

Tags: number theory, binary representation



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)\quad\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}. \]