2020 CIME I Problems/Problem 12

Problem 12

Define a sequence $a_0, a_1, a_2, ...$ by $a_i=\underbrace{1\ldots1}_{2^{i}\text{ 1's}}\underbrace{0\ldots0}_{(2^i-1)\text{ 0's}}1_2,$ where $a_i$ is expressed in binary. Let $S$ be the sum of the digits when $a_0 a_1 a_2 \cdots a_{10}$ is expressed in binary. Find the remainder when $S$ is divided by $1000$ .

Solution

We simply test out some values first. Denote $P(n)=\prod_{i=0}^n a_i$ ; we must find $P(10)$ . Additionally, notice that $P(n)=a_nP(n-1)$ .

We clearly see that $P(0)=a_0=11_2$ . The sum of the digits is $2$ .

Next, we can quickly calculate that $P(1)=a_1P(0)=100111_2$ , whose sum of digits is $4$ .

Then, we can find (after more effort) that $P(2)=a_2P(1)=10010010110111_2$ , whose sum of digits is $8$ .

The above hints towards a pattern; denote the sum of digits of $P(n)$ as $S(n)$ ; we quickly realize due to the $2,4,8$ pattern that we can guess $S(n)=2^{n+1}$ . Calculating $P(3)$ confirms this theory, so we assume that it is true and plug in: $S(10)=2^{11}=2048\rightarrow \boxed{048}$

~ eevee9406

2020 CIME I (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All CIME Problems and Solutions

Page

Toolbox

Search

2020 CIME I Problems/Problem 12

Problem 12

Solution

See also