Consider a set of $2^n-1$ non negative integers $S= ${$ a\_{i,j}|1\le i\le n; 1\le j\le 2^{i-1} $} such that:


\begin{align}{}
1.\ \ &a\_{i,j}\le 2^{n+1-i} \\\\
2.\ \ &a\_{i,j}\le a\_{i-1,j} \\\\
3.\ \ &a\_{1,1}+\sum\_{i=2}^n\left(\sum\_{j=2^{i-2}+1}^{2^{i-1}}{a\_{i,j}}\right)\le 2^n \end{align}
Prove that: $$\sum\_{S}a\_{i,j}\le k2^n$$ in which $k$ is a constant number.



Combinatorial Inequality
The answer is *no*, this is false. Specifically, if we let $m$ be the largest integer such that $(m+2)2^m \le 2^n$, then the largest achievable sum is exactly $2^m (2m+2) + 2^n (n-m-1)$, which is not bounded by any constant multiple of $2^n$, since $n-m$ is not bounded.


Proof:


I'm going to denote the top element of the $j$'th column by $A\_j$. The problem really just deals with how to best choose the $A\_j$, which can sum to at most $2^n$, since the other $a\_{ij}$ have no interaction with each other; they will simply always be chosen to be as large as possible given the $A\_j$. Obviously, we can assume the $A\_j$ sum to exactly $2^n$.


The question then is how to distribute $2^n$ 1's among the various columns. Let's compute how much of an increase to the total sum incrementing $A\_j$ gets you. If we denote the length of the $j$'th column by $\ell\_j$, incrementing $A\_j$ gets you an increase of $\ell\_j - \lfloor \log\_2 A\_j \rfloor$, since you are incrementing the rows which are not already maxed out, and there are $\lfloor \log\_2 A\_j\rfloor$ of those. (Well, this fails if $A\_j$ is 0; then we get an increase of $\ell\_j$. It also fails if $\lfloor \log\_2 A\_j \rfloor > \ell\_j$, but as we'll see there's no reason to ever make $A\_j$ that large.)


The point is, incrementing any particular column yields diminishing returns, so the best strategy is to always increment whichever column will yield the biggest increase right then.


As we begin doing this, we get a total value of


$$ n(1\cdot2) + (n-1)(1\cdot 2+ 1\cdot 2) + (n-2)(1\cdot 4+ 1\cdot 2+ 2\cdot 2) +\\\\ (n-3)(1\cdot 8+1\cdot 4+2\cdot 2+4\cdot 2)+\ldots$$


That is: first we increment the first column twice, each time for an increase of $n$; then we increment the first column twice more and the second column twice, each time for an increase of $n-1$; then we increment the first column four times, the second column twice, and the third and fourth columns twice, each time for an increase of $n-2$; then we increment the first column eight times, the second column four times, the third and fourth columns twice, and the fifth through eighth columns twice, each time for an increase of $n-3$...


So at each step $j>0$, we are making a total of $1\cdot2^j + \sum\_{i=0}^{j-2}2^i 2^{j-1-i} + 2^{j-1}\cdot 2 = (j+3)2^{j-1}$ increments. (The initial repeated $1\cdot$ comes from the fact that there is both only one column of length $n$, and of length $n-1$; the final repeated $\cdot 2$ comes from the fact that one has to increment an $A\_j$ to $2$ before the marginal increase first drops, then by another $2$ to get to $4$.) And each yields an increase of $n-j$. (For $j=0$, we make a total of $2$ increments.)


So let's say we get through $m+1$ complete steps of this process, i.e. the largest $j$ value for which we are able to make all the $(j+3)2^{j-1}$ increments is $m$. Then, applying the identity $\sum\_{k=0}^n k2^k = (n-1)2^{n+1}+2$, we get that after $m+1$ complete steps of this we have used up $2+\sum\_{j=1}^m (j+3)2^{j=1}=(m+2)2^m$ of our available increments. So let $m$ be the largest integer such that $(m+2)2^m \le 2^n$.


So doing this -- and then using the remanining increments on whatever columns will yield an increase of $n-m-1$ -- we get a total value of


$$2n + \sum\_{j=1}^m (n-j)(j+3)2^{j-1} + (2^n-(m+2)2^m)(n-m-1).$$


(Note that $n>m$, since $(n+2)2^n>2^n$, and thus $n-m-1>0$, and we don't have to worry that we've accidentally ventured into the realm where our formula for the value of each increment fails.)


Applying the identity $\sum\_{k=0}^n k^2 2^k = (n^2-2n+3)2^{n+1}-6$, this then comes out to $2^m (2m+2) + 2^n (n-m-1)$, which is our best possible value. In particular, it is at least $2^n (n-m-1)$, and so if it were bounded by some $k 2^n$, then $n-m$ would be bounded by some $k$. But this would mean that there was a constant $k$ such that $(n-k+2)2^{n-k} \le 2^n$, which is false.


**Addendum**: To answer Knot's new question -- is $\sum a\_{ij} / 2^n = O(\log n)$? -- observe that for $n\ge 3$, $m\ge n-\lceil \log\_2 n\rceil$. This is because for $n \ge 3$, $n+2-\lceil \log\_2 n \rceil \le n \le 2^{\lceil \log\_2 n \rceil}$, and so $(n+2-\lceil \log\_2 n \rceil)2^{n-\lceil \log\_2 n \rceil} \le 2^n$. And our sum is at most $2^m 2(m+2) + 2^n (n-m-1) \le 2^n (n-m+1) \le 2^n (\lceil \log\_2 n \rceil + 1)$, so after dividing by $2^n$ it is certainly $O(\log n)$.


**Also**, this is perhaps obvious at this point, but let me add that similar reasoning shows $m\lt n-\lfloor \frac{1}{2} \log\_2 n\rfloor$ and so the best possible sum is in fact $2^n \Theta(\log n)$.


