Problem:
Let x0,x1,x2,… be a sequence of numbers, where each xk is either 0 or 1 . For each positive integer n, define
Sn= ∑k=0n−1xk2k
Suppose 7Sn≡1(mod2n) for all n⩾1. What is the value of the sum
x2019+2x2020+4x2021+8x2022?
Answer Choices:
A. 6
B. 7
C. 12
D. 14
E. 15
Solution:
The binary representation for Sn is the digit string
xn−1xn−2xn−3…x0
The first few rightmost digits can be computed from the given congruence. Indeed, 7S1≡1 (mod2) implies x0=1. Then 7S2≡1(mod4) implies
1≡3x0+3x1⋅2≡3+2x1(mod4),
from which x1=1. Next, 7S3≡1(mod8) implies
1≡7x0+7x1⋅2+7x2⋅4≡7+6+4x2(mod8),
from which x2=1. Finally, 7S4≡1(mod16) implies
1≡7x0+7x1⋅2+7x2⋅4+7x3⋅8≡7+14+12+8x3(mod16),
from which x3=0.\
For n≥3, the rightmost 4 binary digits of Sn+1 are 1000 , as are the rightmost 4 binary digits of 8Sn. Now write
7Sn−1=8Sn−(Sn+1)
and note that because 7Sn−1 is a multiple of 2n, the rightmost n binary digits of 7Sn−1 are all 0 . But, for 1≤k≤n−4, the (k+4) th binary digit from the right of 8Sn−(Sn+1) is xk−xk+3, so xk−xk+3=0. It follows that xk+3=xk for k≥1. Therefore
x2019+2x2020+4x2021+8x2022=x3+2x1+4x2+8x3=0+2⋅1+4⋅1+8⋅0=(A)6.
The problems on this page are the property of the MAA's American Mathematics Competitions