, 2015

Solution:

Answer: 577

We prove that $g(1)+g(2)+\cdots+g\left(2^{n}\right)=1+2^{n-2}(n+1)$ for all $n \geq 1$, giving an answer of $1+2^{6} \cdot 9=577$.

First note that $g\left(2^{n}\right)=1$, and that we can view $0,1, \ldots, 2^{n}-1$ as $n$-digit binary sequences by appending leading zeros as necessary. (Then $g(0)=0$.)

Then for $0 \leq x \leq 2^{n}-1$, $x$ and $2^{n}-x$ are complementary $n$-digit binary sequences (of 0's and 1's), with $x$'s strings of 1's (0's) corresponding to $2^{n}-x$'s strings of 0's (resp. 1's). It follows that $g(x)+g\left(2^{n}-x\right)$ is simply 1 more than the number of digit changes in $x$ (or $2^{n}-x$), i.e. the total number of 01 and 10 occurrences in $x$.

Finally, because exactly half of all $n$-digit binary sequences have 0,1 or 1,0 at positions $k, k+1$ (for $1 \leq k \leq n-1$ fixed), we conclude that the average value of $g(x)+g\left(2^{n}-x\right)$ is $1+\frac{n-1}{2}=\frac{n+1}{2}$, and thus that the total value of $g(x)$ is $\frac{1}{2} \cdot 2^{n} \cdot \frac{n+1}{2}=(n+1) 2^{n-2}$, as desired.

Solution:

We prove that $g(1)+g(2)+\cdots+g\left(2^{n}-1\right)=2^{n-2}(n+1)$.

Identify each block of 1's with its rightmost 1. Then it suffices to count the number of these "rightmost 1's." For each $1 \leq k \leq n-1$, the $k$th digit from the left is a rightmost 1 if and only if the $k$ and $k+1$ digits from the left are 1 and 0 respectively. Thus there are $2^{n-2}$ possible numbers. For the rightmost digit, it is a rightmost 1 if and only if it is a 1, so there are $2^{n-1}$ possible numbers. Sum up we have: $(n-1) 2^{n-2}+2^{n-1}=2^{n-2}(n+1)$, as desired.