HMMT 二月 2026 · 冲刺赛 · 第 15 题

HMMT February 2026 — Guts Round — Problem 15

[9] Compute the number of ways to partition 2026 into the unordered sum of distinct positive integers, each of which is a power of 2 or a power of 6 .

解析

[9] Compute the number of ways to partition 2026 into the unordered sum of distinct positive integers, each of which is a power of 2 or a power of 6 . Proposed by: Sebastian Attlan Answer: 16 10 Solution: The maximum possible power of 2 we can use is 2 , while the maximum possible power of 4 6 we can use is 6 . Therefore, we need to compute the number of subsets S of 1 2 10 1 2 3 4 { 1 , 2 , 2 , . . . , 2 , 6 , 6 , 6 , 6 } whose sum is 2026 . 1 2 3 4 1 2 10 Given any subset B of { 6 , 6 , 6 , 6 } with sum k ≤ 2026 , there is a unique subset A of { 1 , 2 , 2 , . . . , 2 } with sum 2026 − k corresponding to the binary representation of 2026 − k . Hence, each possible B induces a unique possibility for S . 1 2 3 4 Therefore, it suffices to compute the number of subsets B of { 6 , 6 , 6 , 6 } with sum at most 2026 . 4 But it is easy to see that all subsets satisfy this property, so the answer is simply 2 = 16 .