HMMT 十一月 2021 · 冲刺赛 · 第 26 题
HMMT November 2021 — Guts Round — Problem 26
题目详情
- [13] Let X be the number of sequences of positive integers a , a , . . . , a that satisfy all of the following 1 2 2047 properties: • Each a is either 0 or a power of 2. i • a = a + a for 1 ≤ i ≤ 1023. i 2 i 2 i +1 • a = 1024. 1 Find the remainder when X is divided by 100.
解析
- [13] Let X be the number of sequences of integers a , a , . . . , a that satisfy all of the following 1 2 2047 properties: • Each a is either 0 or a power of 2. i • a = a + a for 1 ≤ i ≤ 1023. i 2 i 2 i +1 • a = 1024. 1 Find the remainder when X is divided by 100. Proposed by: Gabriel Wu Answer: 15 Solution 1: This problem can be visualized as a complete binary tree with 16 leaves, such that each node contains the sum of its two children. Let f ( p ) be the number of ways to fill in a binary tree with p p 2 leaves and the root having value 2 . We want f (10). Since all values must be a power of 2, we can 2 set up the recurrence f ( p ) = 2 f ( p − 1) + f ( p − 1) . This is because we have three cases: either all of p the 2 can go to the left child of the root (in which case there are f ( p − 1) ways because even though p p − 1 there’s 2 in the new root, we can treat it as 2 because none of the leaves will have a value of 1), all of the it can go to the right child of the root (another f ( p − 1) ways), or it can be split evenly p 2 2 ( f ( p − 1) ways). This recursion can be shown to be f ( p ) = 2 − 1 by induction. Thus, our answer is 1024 2 − 1 which is 15 modulo 100. Solution 2: The simple formula derived in the previous solution hints at a cute bijection. It turns out that the entire tree is determined by the set of leaf nodes that have non-zero value. You can see this is true: start with the root node, then only split the value each time if both subtrees have a non-zero leaf. The entire process is uniquely determined. Thus, the total number of ways is 2 to the number of leaves, minus one for the case where all of the leaves have zero value. Remark. The original statement superfluously included the condition that a , . . . , a are positive 1 2017 integers, so all teams received points for this problem.