HMMT November, 2014

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

For any positive integers $a$ and $b$ , define $a \oplus b$ to be the result when adding $a$ to $b$ in binary (base 2), neglecting any carry-overs. For example, $20 \oplus 14=10100_{2} \oplus 1110_{2}=11010_{2}=26$ . (The operation $\oplus$ is called the exclusive or.) Compute the sum
$\sum_{k=0}^{2^{2014}-1}\left(k \oplus\left\lfloor\frac{k}{2}\right\rfloor\right)$
Here $\lfloor x\rfloor$ is the greatest integer not exceeding $x$ .

Solution

Solution:

Answer: $\quad 2^{2013}\left(2^{2014}-1\right)$ OR $2^{4027}-2^{2013}$

Let $k=a_{2013} a_{2012} \ldots a_{0}$ in base 2. Then $\left\lfloor\frac{k}{2}\right\rfloor=\overline{0 a_{2013} \ldots a_{1}}$ in base 2. So the leftmost digit of $k \oplus\left\lfloor\frac{k}{2}\right\rfloor$ is 1 if and only if $a_{2013}=1$ , and the $n$ th digit from the right is 1 if and only if $a_{n} \neq a_{n-1}$ ( $1 \leq n \leq 2013$ ).

In either case, the probability of each digit being 1 is $\frac{1}{2}$ . Therefore, the sum of all such numbers is
$\frac{1}{2} \cdot 2^{2014} \cdot \underbrace{11 \ldots 11_{2}}_{2014 \text{ digits }}=2^{2013}\left(2^{2014}-1\right)$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.