Traveling between integers- powers of 2 
Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. 

Consider the integers. We can only travel directly between two integers with a difference whose absolute value is a power of 2 and every time we do this it is called a step. The distance $d$ between two integers is the minimum number of steps required to get from one to the other. Note however that we can travel backwards. For instance $d(2,17)$ is 2: $2+16=18 \rightarrow 18-1=17$. 
How can we prove that for any integer n, we will always have some $d(a,b)=n$ where$b>a$? 

If we are only able to take forward steps I know that  the number of 1s in the binary representation of $b-a$ would be $d(a,b)$. However, we are able to take steps leftward on the number line...

Consider $ a(n) = \sum_0^n 2^{2i} $. Then $ d(0,a(n)) = n + 1 $.
Proof: First, note that in any minimal series of steps, you can only use each power of 2 once at most. If you add it twice at any point, you could get the same result by adding the next higher power once (and if that one was used, iteratively until the first unused one), same for substraction, and obviously adding it once and substracting it once would cancel out entirely, each leading to the same result with less steps.
Also, we can do the steps in arbitrary order, so we can assume we do all additions first.
Consider the binary representation of $ a(n) = 10101...1 $ with $ n+1 $ $1$s. A "step" is equivalent to addition or substraction of a power of $ 2 $, and we start at $ 0 $.
We start with the additions, so we can set any number of bits to $1$, each one being a step. Then we do the substractions, and those in order of magnitude, smallest first.
Any substraction of a power of $ 2 $ will flip all $0$ to $1$ starting at its position and then moving up in significance until the first $1$ is encountered which then is flipped to $0$ (note that this is guaranteed to happen because our target number is positive and so the sum of added powers must be greater than the sum of substracted powers).
Now consider the bits in $a(n)$ starting at lowest significiance. Each $01$ pair in the final sum can only have resulted from one of three situations:


*

*Having the power corresponding to the $1$ in the addition steps.

*By resulting from $10$ and substraction of the power of $2$ corresponding to the $01$ bit pair or a lower power of $2$. But in that case, that $10$ must result from addition or substraction of that power of $2$. 

*Or, lastly, as a result of a substraction of a lower power of $2$ from $00$. But in that case, the result of the substraction would have been $11$ and thus, the power of two corresponding to the $0$ in that pair must also be substracted.
In 2. and 3. we made use of the fact that we can only use each power of $2$ once at most, so once a $1$ occurs at a point, substractions from below cannot go beyond it (as $ \sum_{i \lt n} 2^i \lt 2^n $).
Thus, we require at least one step for each $01$ pair and the claim is proven.
Additionally, any number $ b $ with $ d(0,b) = n+1 $ must at least have $ 2n $ digits: Assume $ b $ had less than $ 2n $ digits in binary representation. If $b$ contains $n$ or less 1s, we are done. And if there are at least $n+1$ $1$s  and thus at most $ n-2 $ $0$s, then we have a procedure to generate $ b $ in $n$ steps: Start with $2^{2n}-1$ in two steps resulting in $1...1$, and then in an additional $n-2$ substractions we substract all powers of $2$ that correspond to a $0$ in the binary representation of $b$. As $d(0,1011_b)=3$ shows, there are numbers with just $2n$ digits, though, so $a(n)$ is not optimal.
