Not quite binary

Number Theory Level 3

Find the number of ways of expressing $n=2017$ as

$a_0 + a_1 2 + a_2 2^2 + a_3 2^3 + \cdots + a_k 2^k$

$a_i \in \{0,1,2\}$ .

The answer is 25.

1 solution

Brian Moehring
Jun 28, 2018

I'll not prove my statements, but I'll give the idea (I think everything can be proven directly without complicated methods, but it looks to be messy):

Starting with a binary representation, there are two types of changes that can happen (all of the following are numbers written in base 2, but we allow the digit $2$ , so it's not properly binary):

$\ldots 100\ldots 000\ldots$ becomes $\ldots 011\ldots 112\ldots$
$\ldots 111\ldots 110\ldots$ becomes $\ldots 022\ldots 222\ldots$

Note that $2017$ in binary is $11111100001$ . Therefore we can either leave the representation unchanged or change it. If we decide to change it, then we must choose one of the four $0$ s to become a $2$ and we must choose one of the six consecutive $1$ s to become a $0$ . It follows that there are $4\cdot 6 = 24$ ways to change the representation. Adding this to the unchanged representation gives an answer of $24 + 1 = \boxed{25}$ .

Not quite binary

The answer is 25.

1 solution

0 pending reports