MathDB
A binary representation problem

Source: Vietnam TST 2016 - P5

July 29, 2016
number theorybinary representation

Problem Statement

Given nn numbers a1,a2,...,ana_1,a_2,...,a_n (n≥3n\geq 3) where ai∈{0,1}a_i\in\{0,1\} for all i=1,2.,,,.ni=1,2.,,,.n. Consider nn following nn-tuples S1=(a1,a2,...,an−1,an)S2=(a2,a3,...,an,a1)⋮Sn=(an,a1,...,an−2,an−1). \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=(b1,b2,...,bn)r=(b_1,b_2,...,b_n), let ω(r)=b1⋅2n−1+b2⋅2n−2+⋯+bn. \omega (r)=b_1\cdot 2^{n-1}+b_2\cdot 2^{n-2}+\cdots+b_n. Assume that the numbers ω(S1),ω(S2),...,ω(Sn)\omega (S_1),\omega (S_2),...,\omega (S_n) receive exactly kk different values.
a) Prove that k∣nk|n and \frac{2^n-1}{2^k-1}|\omega (S_i) \forall i=1,2,...,n.
b) Let M=max⁡i=1,n‾ω(Si)m=min⁡i=1,n‾ω(Si). \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≥(2n−1)(2k−1−1)2k−1. M-m\geq\frac{(2^n-1)(2^{k-1}-1)}{2^k-1}.
Back to ProblemsView on AoPS