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=0∑n−1​xk​2k
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−1​xn−2​xn−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