3
$\begingroup$

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.

$\endgroup$
6
  • 5
    $\begingroup$ Why should anyone want to prove that ...? $\endgroup$ Feb 15, 2013 at 22:53
  • 2
    $\begingroup$ OK, I will have to type up the details as an answer later, but I think this is false. According to my computations (warning: untested), if $m$ is the largest integer such that $(m+2)2^m\le 2^n$, then the best possible sum you can get is given by $4n+2^m(2m+2)+2^n(n-m-1)$. Obviously the first two terms can be bounded by some $k2^n$, but the last can't, because that would mean there was some k such that $m\ge n-k$, i.e. $(n-k+2)2^(n-k)\le 2^n$, which is false. $\endgroup$ Feb 16, 2013 at 11:23
  • 1
    $\begingroup$ Indeed, the answer in no. There are simple examples which show that $k$ is not bounded. In these examples one can even choose $a_{i,r}=a_{i,s}$ if $2^{t-1}\lt r,s\le 2^t$, reducing to a system in $n(n+1)/2$ variables. As Harry Altman announced a solution, I won't put it here. $\endgroup$ Feb 16, 2013 at 18:22
  • $\begingroup$ Go ahead and post your solution; hopefully it's simpler than mine. I found the best possible sum (note: it is not quite what I stated in the comment above, I miscomputed), but maybe there is a simpler example... $\endgroup$ Feb 17, 2013 at 0:59
  • $\begingroup$ It seems to me that $\frac{\sum a_{ij}}{2^n}=O(\log n)$. Is it correct? $\endgroup$
    – Knot
    Feb 17, 2013 at 9:39

1 Answer 1

6
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.