Call the improvement of a positive number its replacement by a power of two. (i.e. one of the numbers $1, 2, 4, 8, ...$), for which it increases, but not more than than $3$ times. Given $2^{100}$ positive numbers with a sum of $2^{100}$. Prove that you can erase some of them, and improve each of the other numbers so that the sum the resulting numbers were again $2^{100}$.
Problem
Source: St. Petersburg 2019 9.5
Tags: combinatorics, Sum, algebra, number theory
14.08.2020 12:58
We employ a greedy algorithm. Enumerate the numbers $a_1 \geq a_2 \geq a_3 \cdots \geq a_{2^{100}}$. Consider the following algorithm. Let $b_1$ be the greatest power of two in the range $(a_1, 3a_1)$ less than or equal to $2^{100}$. Now we recursively define $b_k$ and $S_k$. Let $S_k = b_1 + b_2 + \cdots + b_k$. Then let $b_{k+1}$ be the greatest power of two in $(a_{k+1}, 3a_{k+1})$ such that $S_{k} + b_{k+1} \leq 2^{100}$. Terminate the process when $S_k = 2^{100}$ (possibly at $k=1)$. Improve all the $a_i$ to $b_i$ for $i \leq k$ and erase $a_i$ for $i > k$. It remains to establish a few facts. First, there must exist some $k$ such that $S_k \geq 2^{100}$. Otherwise, \[ 2^{100} > S_{2^{100}} = b_1 + b_2 + \cdots + b_{2^{100}} > a_1 + a_2 + a_{2^{100}} = 2^{100} \]which is a contradiction. Second, it is impossible that there does not exist a power of two $b_{k+1}$ in the range $(a_{k+1}, 3a_{k+1})$ with $S_k + b_{k+1} \leq 2^{100}$. Obviously, there exists a power of two in this range, so it suffices to show that it cannot be more than $2^{100} - S_k$. Because $b_1, b_2, \cdots b_k$ are powers of two at least $b_{k+1}$, we can take $S_k \pmod{b_k}$ to check that $2^{100} - S_k \geq b_k$.
26.02.2021 13:25
Call a positive real number $n$ being at $k$-stage if $2^k\le n <2^{k+1}$. That means if we improve a $k$-stage number, it will become $2^{k+1}$. Now use the algorithm below, if two number $a, b$ are in the same stage(we say $k$), then erase two numbers and replace them it $a+b$. Notice that $a+b$ is $k+1$-stage number, so the improvement of $a+b$ is $2^{k+1}$, as same as we improve $a$, $b$ respectively and sum them up. So we only have to guarantee the numbers we get satisfy the question (just do the algorithm backward). And also, the algorithm doesn't change the sum of all numbers. $\qquad$ If at any moment, we get a $99$-stage number, we are definitely done, just improve it and delete the rest number. Else, we just do the algorithm til we can't do it anymore (it does stop because the $2^{100}$ is finite), and we still don't have a $99$-stage number.However, that means the sum of all number $<2^{99}+2^{98}+\cdots < 2^{100}$, which is ridiculous.