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}. \]
Problem
Source: Vietnam TST 2016 - P5
Tags: number theory, binary representation
29.07.2016 10:54
a) Let $\ell$ is smallest positive integer such that $a_i=a_{i+\ell}$ for all $i=1,2,...,n$ (exists since $a_i=a_{i+n}$). First, we will prove that $\ell \mid n$, and then $k=\ell$. Suppose that $\ell\nmid n$ we get that there exist $0<r<\ell$ such that $n=\ell q+r$ for some $q\in \mathbb{Z}^+$. For each $i=1,2,...,n$, we get that $a_{i+1}=a_{i+(\ell-r+1)}$. And since $0< \ell-r <\ell$, this contradict the definition of $\ell$. Hence, $\ell\mid n$ For all tuples $r_1=(a_{x+1},a_{x+2},...,a_{x+n}),r_2=(a_{y+1},a_{y+2},...,a_{y+n})$ that $\omega (r_1)=\omega (r_2)$: We clearly get that for all $i=1,2,...,n$, $a_i=a_{i+(y-x)}$. So $|y-x| \geq \ell$. So, all of tuples $r_j= (a_{j+1},a_{j+2},...,a_{j+n})$ where $j=1,2,...,\ell$ give distinct values of $\omega (r)$. We also get that for all $x\in \{ 1,2,...,n\}$, $\omega ((a_{x+1},a_{x+2},...,a_{x+n})) =\omega (r_j)$ for $j\in \{ 1,2,...,\ell\}$ that $j\equiv x\pmod{\ell}$. Hence, $k=\ell$. Finally for all $i=1,2,...,k$, $\omega (S_i)=(2^{k(t-1)}+2^{k(t-2)}+...+2^0)(a_i2^{k-1}+a_{i+1}2^{k-2}+...+a_{i+(k-1)}2^0) =\frac{2^n-1}{2^k-1} \Big( a_i2^{k-1}+a_{i+1}2^{k-2}+...+a_{i+(k-1)}2^0 \Big)$ where $t=n/k$, and we are done.
29.07.2016 10:57
A)Obvious $\omega(S_i)=\omega(S_j) \to (a_i,a_{i+1},...a_{i-1})=(a_j,a_{j+1},...a_{j-1})$ or $S_i=S_j$ and $S_{i+l}=S_{j+l}$, so let $k$ -minimal number ,such $S_1=S_{k+1}$, obvious ,that $\omega(S_i)$ receive exactly $k$ different values. $S_{n+1}=S_1$ $S_{i}$ is periodic with period $k$, and $S_{k+1-l}=S_{n+1-l}$ so $k|n$ Obvious, that if $\frac{2^n-1}{2^k-1}|\omega (S_1)$ than $\frac{2^n-1}{2^k-1}|\omega (S_i)\quad\forall i=1,2,...,n$ (because , we can build new sequence $S_1^`=S_i,S_2^`=S_{i+1}....S_n^`$ with same properties $S_1=S_{k+1} \to a_1=a_{k+1},a_2=a_{k+2}...$ $\omega(S_1)=a_1\cdot 2^{n-1}+a_2\cdot 2^{n-2}+\cdots+a_n=a_1\cdot 2^{n-1}+a_2\cdot 2^{n-2}+\cdots+a_k\cdot 2^{n-k}+a_1\cdot 2^{n-k-1}+\cdots = (a_1\cdot 2^{k-1}+a_2\cdot 2^{k-2}+\cdots+a_k)2^{n-k}+(a_1\cdot 2^{k-1}+a_2\cdot 2^{k-2}+\cdots+a_k)2^{n-2k}+\cdots = (a_1\cdot 2^{k-1}+a_2\cdot 2^{k-2}+\cdots+a_k)(2^{n-k}+2^{n-2k}+...+1)=(a_1\cdot 2^{k-1}+a_2\cdot 2^{k-2}+\cdots+a_k) \frac{2^n -1}{2^k-1}$
29.07.2016 12:20
Ignore this.