Let $m$ and $n$ be positive integers, where $m < 2^n.$ Determine the smallest possible number of not necessarily pairwise distinct powers of two that add up to $m\cdot(2^n- 1).$ The Problem Selection Committee
Problem
Source: Romania TST 2023 Day 1 P1
Tags: number theory, sum of digits
07.04.2024 17:40
Very well-known that $s_2(m(2^n-1))=n$ for $m<2^n$, and the answer follows.
08.04.2024 03:41
We just need to find how many $1$ there are in binary representation of $m\cdot(2^n- 1).$ Let $$m = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}$$be the binary representation of $m$ where $a_1< a_2 < \dots < a_k < n$. Then \begin{align*} m\cdot(2^n- 1) = m\cdot 2^n - m &= 2^{n + a_1} + 2^{n + a_2} + \cdots + 2^{n + a_k} - 2^{a_1} - 2^{a_2} - \cdots- 2^{a_k}\\ &= 2^{n + a_2} + \cdots + 2^{a_k} + 2^{a_1}\cdot (2^n - 1) - 2^{a_2} - \cdots- 2^{a_k}\\ &= 2^{n + a_2} + \cdots + 2^{n + a_k} + 2^{a_1}\cdot (1 + 2 + 2^2 + \cdots + 2^{n-1}) - 2^{a_2} - \cdots- 2^{a_k}\\ & = 2^{n + a_2} + \cdots + 2^{n + a_k} + (2^{a_1} + 2^{a_1 + 1} + 2^{a_1 + 2} + \cdots + 2^{a_1 + n-1}) - 2^{a_2} - \cdots- 2^{a_k} \end{align*}Since $a_1 < a_2 < a_k \leq n-1 \leq a_1 + n - 1$ we have $$\{a_2, a_3 , \dots, a_k\} \subseteq \{a_1, a_1+ 1, a_1 + 2, \dots, a_1 + n-1 \}$$So, $k-1$ of numbers inside the bracket cancel out with $k-1$ powers of two with negative signs . Moreover, powers of two inside the bracket all are $\leq a_1 + n - 1 < a_2 + n < \cdots < a_k + n$. So after cancellation of powers with negative signs we get exactly $n$ distinct powers of $2$. So the answer is $n$.
08.04.2024 09:59
Related to apmo 2016 p2
08.04.2024 16:55
We will note with $s_2(x)$ $=$ the sum of the digits of the number x in base 2. We will prove that $s_2(m\cdot(2^n-1))=n$ for $m<2^n$. $s_2(m\cdot(2^n-1))=s_2((m-1+1)\cdot(2^n-1))=s_2((m-1)\cdot2^n+(2^n-1) - (m-1))=s_2(m-1)+n-s_2(m-1)=n$.So the minimum required is n.