My solution: a) Let $n=2^{a_1}+...+2^{a_m}$ be binary representation of $n$. We have that $n=2^{a_1}-2^{a_2}+2^{a_2+1}-2^{a_3}+2^{a_3+1}+...+2^{a_m+1}$ and if some of $a_i+1=a_{i+1}$ they would disappear so we are left with sum that is exactly like the one in statement. Now assume that there two different representations of $n=\sum_{j=1}^{2k+1}(-1)^{j-1}2^{m_j}= \sum_{j=1}^{2t+1}(-1)^{j-1}2^{n_j}$. $V_2(n)=m_1=n_1$$\implies$ $m_1=n_1$. Assume $m_i=n_i$. We have that $V_2(n+\sum_{j=1}^{i}(-1)^j2^{m_j})=m_{i+1}=n_{i+1}\implies$ $m_{i+1}=n_{i+1}$. Therefore the representation is uniqe. b) Note that the weight of $ n=2^{a_1}+...+2^{a_m}$ is equal to $m-1-|\{i, i\neq 1\wedge a_{i}+1=a_{i+1}\}|$. That implies that the number of numbers less or equal to $2^{n+1}$ having weight even is equal to number of subsets $X$ of $0,1,...,n-1,n$ for which$|X|-$(number of pairs with difference 1 excluding pair with smallest number) is even. So we have that the number $a_n$: difference between the numbers with even weight and odd weight that are less or equal to $2^n$ satisfies $a_n=a_{n-1}-2a_{n-3}$ with $a_1=a_2=2$. That implies $a_{2017}=2^{1009}$.

a) Ok, so we want to jump from interval $[1,2^{m}]$ onto $[2^{m}+1,2^{m+1}].$ Let $x$ be in first interval that satisfies desired condition. Consider now $x+2^{m+1}-2^{k}$ for some $k.$ We want $k$ such that $2^{m}+1 \le x+2^{m+1}-2^{k} \le 2^{m+1} \iff -2^m+1 \le x-2^{k} \le 0.$ So if we have some $x'$ composed of sum of even number of distinct powers of 2 such that $-2^m+1 \le x' \le 0$ we can jump from $[1,2^{m}]$ onto $[2^{m}+1,2^{m+1}].$ So now we want to prove that we can jump from $[1,2^{m}]$ onto $[2^{m}+1,2^{m+1}]$ and from $[0,-2^{m}+1]$ onto $[-2^{m},-2^{m+1}+1],$ in the same time (base is skipped here). Case 1: $x$ is in $[1,2^{m}] \cup [0,-2^{m}+1]$ but this is true by inductive hypothesis (IH). Case 2: $x$ is in $[2^{m}+1,2^{m+1}]$ then take $x'=x-2^{m+1}$ and it reduces to IH. Case 3: $x$ is in $[-2^{m},-2^{m+1}+1]$ then take $x'=x+2^{m+1}$ and it reduces to IH. Hence, only thing left to prove is the uniqueness of representation, which as a matter of fact, could've been squeezed in induction (if $x,y$ have different representations then $x + 2^{m+1}$ and $y+2^{m+1}$ have different representations, as well). b) Only $m_i$'s that are to appear here are from $(1,2,3,...,2016,2017)$ and clearly there must be (by part a)) bijection from subsets of odd cardinality of set $(1,2,3,...,2016,2017)$ and all possible representations. Hence, we are actually looking for $A-B$ where $A$ is number of subsets such that their cardinality is $\equiv 1 \pmod 4$ and $B$ such that $\equiv 3 \pmod 4.$ But this is trivial using roots of unity filter or whatever.

Nice tutorial problem! Took me embarrassingly long (thanks to an interesting but false lead). For existence, write $n=2^{a_1}+2^{a_2}+\dots+2^{a_j}$ for $a_1>a_2>\dots>a_j \ge 0$ and note that $$n=2^{a_1+1}+\left(-2^{a_1}+2^{a_2+1}\right)+\left(-2^{a_2}+2^{a_3+1}\right)+\dots+\left(-2^{a_{j-1}}+2^{a_j}\right).$$Removing the brackets which add up to zero, we get a valid representation for $n$. For uniqueness, proceed by induction on $n$. Small values work, so we may proceed to the induction step. Excluding powers of $2$ (for which uniqueness is easy to show by considering $v_2$'s), we may assume $2^l<n<2^{l+1}$. Note that in such a representation $m_1=v_2(n)$ and, $$2^{m_{2k+1}-1} \le 2^{m_{2k+1}}-2^{m_{2k}}<n<2^{m_{2k+1}}.$$It follows that $m_{2k+1}=l+1$. We have to show that $2^{l+1}+2^{m_1}-n$ is uniquely expressive in that form, which follows by the induction hypothesis since $n>2^l$ and $v_2(n)=m_1 \Longrightarrow$ $n \ge 2^l+2^{m_1},$ so $2^{l+1}+2^{m_1}-n \le 2^l <n$. Finally, for the counting argument, note that in the range $[1, 2^L]$ we have even weight numbers as ones where the number of summands is $1 \pmod {4}$ whereas for odd weight numbers we have number of summands as $3 \pmod {4}$. It follows that the desired difference is given by $$\sum_{k \ge 0} \binom{M+1}{4k+1}-\sum_{k \ge 0} \binom{M+1}{4k+3}=\frac{(1+i)^{M+1}-(1-i)^{M+1}}{2i}=2^{\frac{M+1}{2}}\cdot \sin \frac{(M+1)\pi}{4}.$$The last sum is obtained by the roots of unity filter and it evaluates to $2^{1009}$. Note: The so called "false lead" was that the weight can be expressed as the number of $1$ blocks in the binary representation of $n$ with a small adjustment. This makes the otherwise easy part b.) harder to count.

Problem 1. Sketch of my solution in the mock contest. (a). First, by bounding the sum, one can easily get $2^{m_{2k+1}-1} < n \le 2^{m_{2k+1}}$. Also note that $m_1=v_2(n)$. This gives us that given $n$, we can uniquely decide $m_1$ and $m_{2k+1}$. Strong Induct on $n$. Base case is trivial. If $n=2^v$, clearly there is a unique way to express $n$. One can easily show that $1 \le |n-2^{m_1}-2^{m_{2k+1}}| < n$, so by the induction hypothesis we know that there is a unique way to express $|n-2^{m_1}-2^{m_{2k+1}}|$. Let's say $m'_1$ and $m'_{2k'+1}$ are the $m_1$, $m_{2k+1}$ in the unique representation of $|n-2^{m_1}-2^{m_{2k+1}}|$. Clearly $m'_1>m_1$ by $v_2$ calculation, and one can show $m'_{2k'+1} < m_{2k+1}$ by bounding. Now it is clear that the unique way to represent $n$ is to select $m_1 < m'_1 < m'_2 < \cdots < m'_{2k'+1} < m_{2k+1}$, which completes the induction. (b). Let's look at $2^{n-1} < x \le 2^n$. These values will have representations starting with $2^n- \cdots $. Therefore, one can simply choose even number of numbers between $0$ and $n-1$ inclusive. We can easily see that the number of numbers with even weight is just $\sum_{k=0}^\infty \binom{n}{4k}$, and number of numbers with odd weight is just $\sum_{k=0}^\infty \binom{n}{4k+2}$. We need to add this from $0$ to $2017$. Using Pascal, we can easily transform this sum to $\sum_{k=0}^\infty \binom{2018}{4k+1}-\binom{2018}{4k+3}$. Using binomial expansion, we can show that this value is just the imaginary part of $(1+i)^{2018}$, or $2^{1009}$.

I'll solve just (a), which has a nice algorithmic flavour; (b) is just a boring summation that can be nuked with standard techniques. Of course, we'll induct on $n$; more specifically, it'll be strong induction. Small values of $n$ are not a problem; let's say we want to represent $n>1$ and also prove that representation is unique. To make our thoughts concrete, let's flesh out the summation:$$n=2^{m_{2k+1}}-2^{m_{2k}}+\cdots +2^{m_3}-2^{m_2}+2^{m_1}.$$Obviously, if $n$ is even, then $\nu_2(n)=m_1$, so we can (and must) divide both sides by $2^{m_1}$ to obtain a representation of $\frac{n}{2^{m_1}}<n$, which exists and is unique by induction hypothesis. On the other hand, $n\equiv1\pmod{2}$ means $m_1=1$, so then $m_2=\nu_2(n-1)$. The equation can be rewritten as $$2^{m_{2k+1}-m_2}-2^{m_{2k}-m_2}+\cdots +2^{m_3-m_2}=\frac{n-1}{2^{m_2}}+1.$$Conveniently enough, the LHS is now a representation for $\frac{n-1}{2^{m_2}}+1<n$, which is existent and unique. It now remains to go backwards and get a unique representation for $n$ itself. $\blacksquare$ Given just how algorithmic this problem smells, it's no surprise that we can have a recursive formula for $w(n)$, the weight of $n$:$$\left.\begin{array}{c}w(1)=1\\ w(2n)=w(n)\\ w\left(2^kn+1\right)=w(n+1)+1\end{array}\right\}$$ What's even more interesting, here's a quick python snippet for calculating $m_i$'s and the weight for any given $n$. def power(n): p=1 while n%2==0: n=n/2 p=p*2 return pdef represent(n): if n==1: return [1] if n%2==0: return [2*i for i in represent(n/2)] if n%2==1: p=power(n-1) return [p*i for i in represent((n-1)/p+1)]+[p,1]x=int(input("Type in a positive integer:"))a=represent(x)print("The m_i's are:",a,". The weight is ", int((len(a)-1)/2),".")def power(n): p=1 while n%2==0: n=n/2 p=p*2 return p def represent(n): if n==1: return [1] if n%2==0: return [2*i for i in represent(n/2)] if n%2==1: p=power(n-1) return [p*i for i in represent((n-1)/p+1)]+[p,1] x=int(input("Type in a positive integer:")) a=represent(x) print("The m_i's are:",a,". The weight is ", int((len(a)-1)/2),".")RunResetPop Out /

My solution: We use induction and that too strong. The base case is trivial. Now we know that for $n \in [1,2^k]$ we have a representation. So take an $n\in [2^{k+1}-2^i+1, 2^{k+1}-2^{i-1}]$. Set m to be $n-2^{k+1}+2^i$. We have a representation for m and so for n. Also $2^{k+1}$ has a trivial representation so we are done. Now we prove the uniqueness. We know that the number of representations less than $2^k$ are $2^k$ (take any combination of exponents from 0 to k-1). Since the upper bounds and lower bounds match, there is exactly one representation for each number. For the count, observe we need to find the imaginary part of $(1+i)^{2018}$ and thus we are done as this is precisely $2^{1009}$.

For part (a) we simply remark that the representation corresponds exactly to maximal contiguous blocks of length $1$ in the binary representation of $n$, after the trailing $10\dots0$ is excised. The weight $k$ then denotes the number of such $1$-blocks. For (b), for each $m \ge 1$ we let $d_m$ be the difference between the number of binary strings of length $m$ with an even number of $1$-blocks minus the number with an odd number of $1$-blocks. We will now compute $d_m$. Consider strings with exactly $b$ blocks, $1 \le b \le m$. If $b$ is even, then exactly $b/2$ of the blocks are all $1$, hence the number of blocks is even iff $b \equiv 0 \pmod 4$. Moreover there are $2\binom{m-1}{b-1}$ such strings. Hence we obtain \[ \sum_{b \equiv 0 \pmod 4} 2\binom{m-1}{b-1} = \sum_{a \equiv 3 \pmod 4} 2\binom{m-1}{a} \]strings with an even number of $1$-blocks, and $\sum_{a \equiv 1 \pmod 4} 2 \binom{m-1}{a}$ with an odd number. If $b$ is odd, then half the strings will have an odd number of $1$'s and the other half will have an even number of $1$'s. Hence we obtain \[ d_m = \sum_{a \equiv 3 \pmod 4} 2\binom{m-1}{a} - \sum_{a \equiv 1 \pmod 4} 2\binom{m-1}{a} = \frac{2(1-i)^{m-1} - 2(1+i)^{m-1}}{2i}. \]Then, \begin{align*} \sum_{m=1}^{2016} d_m &= \frac{1}{i} \sum_{m=1}^{2016} (1-i)^{m-1} - (1+i)^{m-1} \\ &= \frac{1}{i} \left[ \frac{1-(1-i)^{2016}}{1-(1-i)} - \frac{1-(1+i)^{2016}}{1-(1+i)} \right] \\ &= (1+i)^{2016} + (1-i)^{2016} - 2 \\ &= -2 + (2i)^{1008} + (-2i)^{1008} = 2 + 2^{1009}. \end{align*}Finally in light of exceptional values $n = 2^{2016}$ and $n = 2^{2017}$, both of weight zero, we obtain the final answer $2^{1009}$.

v_Enhance wrote: remark that the representation corresponds exactly to maximal contiguous blocks of length $1$ in the binary representation of $n$, after the trailing $10\dots0$ is excised. The weight $k$ then denotes the number of such $1$-blocks. Okay, I got this, but I got caught up trying to figure out how to deal with the trailing $10\dots0$ being removed. Why are we able to move on counting blocks as the above solution does? For example the number $10=1010_2$ ends with a final $10$, and so it's value is 1, and not 2, even though the amount of blocks is divisible by 4. Edit: I get it now: anantmudgal09 wrote: Note: The so called "false lead" was that the weight can be expressed as the number of $1$ blocks in the binary representation of $n$ with a small adjustment. This makes the otherwise easy part b.) harder to count.

We define the alternating binary form to be the same as the binary form of a number but every other $1$ in the string is multiplied by $-1$. So $1110 \rightarrow 2^3-2^2+2^1 = 6$. (a) We claim a bijection between every possible alternating binary form to its binary form. From alternating binary form to binary form is easy as we can simply convert it to a number and from there, convert to its binary form. To convert from binary to alternating, we first ignore the very first $1$ in the string, looking from right to left. Note that a string of $1$'s like $0111111$ from binary will turn into $1000001$. We continue to replace these strings of $1$'s until we converted all the strings of $1$, giving us an alternating form, thus establishing a bijection. (b) Note that the number of ways to have an even weight with a length $n$ alternating binary string is \[\binom{n-1}{0}+\binom{n-1}{4}+\cdots\]and the number of ways to have an odd weight with length $n$ is \[\binom{n-1}{2}+\binom{n-1}{6}+\cdots\]Summing these over lengths $1, 2, \cdots, 2017$, gives us \[-\biggl(\binom{2018}{3}+\binom{2018}{7}+\cdots\biggr) + \biggl(\binom{2018}{1}+\binom{2018}{5}+\cdots\biggr)\]by Hockey Stick. This is the imaginary part of $(1+i)^{2018}$ which is $\boxed{2^{1009}}$ by de Moivre's.