5

Let $0\leq a_1\leq a_2\leq\dots\leq a_n\leq b$ be integers such that $4^b\leq 4^{a_1}+\dots+4^{a_n}$. Can $4^b$ always be written as a sum of some subset of $4^{a_1},\dots,4^{a_n}$?

I think it might be possible to perform some sort of greedy algorithm, where we collect four identical powers of $4$, whenever such exist, into a greater power of $4$. We can perform this process starting from the smallest power of $4$ until it is no longer possible, so we end up with at most three powers of $4$ for each power.

pi66
  • 7,164

2 Answers2

3

Your idea is ok. But true, that it needs some 'formalization'. We suppose $a_n<b$ (or else nothing to show). You may write in base 4 expansion $$4^b \leq \sum_i 4^{a_i}=\sum_{k=0}^{b-1} p_k 4^k+n_b 4^b$$ with each $0\leq p_k\leq 3$ and $n_b\geq 0$. We will construct by induction coarser and coarser (sub-) partitions of the set of $a_i$'s. In the beginning we set $S_0=([a_1],...,[a_n])$ in which each $a_i$ is a one element partition. The value of each element of a partition is the sum of the 4th power of its elements. In $S_0$ each element therefore has a value of the form $4^k$, with $0\leq k<b$.

If $0<p_0$ (remember $p_0$ is not greater than 3) then there must be $p_0$ elements of the partition $S_0$ of value $1$ (i.e. having $a_i=0$). You put those elements aside. The rest you regroup into the smallest possible partition elements to form multiples of 4. Call $S_1$ this new partition. The value of each element is then of the form $4^k$ with $1\leq k<b$.

If $0<p_1 (\leq 3)$ there must be $p_1$ of the elements in $S_1$ with value $4$ which you may set aside. The rest you regroup into a partition $S_2$ where each element of the partition has a value of the form $4^k$ with $2 \leq k<b$, etc...

In $S_{b-1}$ each partition element must have value $4^{b-1}$. If you have 4 of such elements then their union constitute a solution to your problem. If not then there are at most 3 such elements and adding the values of all you have set aside you get $$ \sum_i 4^{a_i} \leq \sum_{k=0}^{b-1} 3 \times 4^k < 4^b$$ contradicting the hypothesis. (Making a drawing of such partitions may help getting the idea).

H. H. Rugh
  • 35,236
3

By induction on $b\geq 0$. The basic step is trivial.

For $b>1$, assume that the statement is true for $b-1$. We have two cases.

i) $a_1\geq 1$ then take $A_i=a_i-1$, by the the inductive step $4^{b-1}$ can be written as a sum of some subset of $4^{A_1},\dots,4^{A_n}$ and then by multiplying by $4$ we get a representation of $4^{b}$.

ii) Assume that $a_1=\dots=a_r=0$ and $a_{r+1}\geq 1$ and assume that $4^{b-1}$ can not be written as a sum of some subset of $4^{A_{r+1}},\dots,4^{A_n}$ (otherwise we ara done as in i)). This means that $$4^{b-1}> 4^{A_{r+1}}+\dots+4^{A_n}\quad \Rightarrow \quad 4^{b}> 4^{a_{r+1}}+\dots+4^{a_n}.$$ But we know that $4^{b}\leq r+4^{a_{r+1}}+\dots+4^{a_n}$. Hence $$4^{b}=4^{a_{1}}+\dots+4^{a_j}+4^{a_{r+1}}+\dots+4^{a_n}$$ where $1\leq j=4^{b}-(4^{a_{r+1}}+\dots+4^{a_n})\leq r$.

P.S. This approach gives you also a recursive algorithm which generate such representations.

Robert Z
  • 145,942