PUMaC 2019 · 代数（A 组） · 第 6 题

6. A weak binary representation of a nonnegative integer n is a representation n = a + 2 · a + 0 1 2 2 · a + . . . such that a ∈ { 0 , 1 , 2 , 3 , 4 , 5 } . Determine the number of such representations for 2 i

Proposed by: Frank Lu Answer: 3290 Let N ( k ) be the number of such representations for k . We know that N (0) = 1 , N (1) = 1 , N (2) = 2 , N (3) = 2, and N (4) = 4. We can see, based on the choice of a , that N (2 k ) = 0 N (2 k +1) = N ( k )+ N ( k − 1)+ N ( k − 2). To make use of this recurrence relation, we define two sequences. First, define x = N (2 k ). Observe then that x − x = N (4 k ) − N (4 k − 2) = k 2 k 2 k − 1 N (2 k ) − N (2 k − 3) = x − x , and that x − x = x − x by a similar token. Now, let k k − 2 2 k +1 2 k k k − 1 y = x − x . Then, our recurrence relation becomes y = y and that y = y + y . k k k − 1 2 k +1 k 2 k k k − 1 From our earlier cases before we see that y = 1 and y = 2. Based on the recurrence in the 1 2 odd case, we see that y k = 1 for each integer i . 2 − 1 k 2 − 2 ∑ k − 1 Claim: y = 3 . i k − 1 i =2 − 1 2 Proof: We inductively show this. For k = 2 we can easily verify this. Now, given the k k +1 k k 2 − 2 2 − 2 2 − 1 ∑ ∑ ∑ case, note that y = y + y . Using our recurrence, this becomes i 2 i +1 2 i k k − 1 k − 1 i =2 − 1 i =2 − 1 i =2 k k k 2 − 1 2 − 1 2 − 1 ∑ ∑ ∑ y + y + y . But knowing that y k = y k − 1 = 1 yields that this i i i − 1 2 − 1 2 − 1 k − 1 k − 1 k − 1 i =2 − 1 i =2 i =2 k 2 − 2 ∑ k − 1 k is just 3 ∗ y = 3 ∗ 3 = 3 , proving the inductive case and proving the claim. i k − 1 i =2 − 1 256 ∑ Finally, observe that N (513) = N (512) = x = x + y , which using our claim is just 256 0 i i =1 2 7 1 + 3 + 3 + . . . + 3 + y + y . A final observation that y = k + 1 yields the answer 255 256 2 ∗ k 8 (3 − 1) / 2 + 1 + 9 = 3290 .