HMMT 十一月 2022 · GEN 赛 · 第 8 题

HMMT November 2022 — GEN Round — Problem 8

Compute the number of sets S such that every element of S is a nonnegative integer less than 16, and if x ∈ S then (2 x mod 16) ∈ S.

解析

Compute the number of sets S such that every element of S is a nonnegative integer less than 16, and if x ∈ S then (2 x mod 16) ∈ S. Proposed by: Vidur Jasuja Answer: 678 Solution: 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 For any nonempty S we must have 0 ∈ S . Now if we draw a directed graph of dependencies among the non-zero elements, it creates a balanced binary tree where every leaf has depth 3. In the diagram, if a is a parent of b it means that if b ∈ S , then a must also be in S . We wish to find the number of subsets of nodes such that every node in the set also has its parent in the set. We do this with recursion. Let f ( n ) denote the number of such sets on a balanced binary tree of depth n. If the root vertex is not in the set, then the set must be empty. Otherwise, we can consider 2 each subtree separately. This gives the recurrence f ( n ) = f ( n − 1) + 1 . We know f (0) = 2, so we can calculate f (1) = 5 , f (2) = 26 , f (3) = 677 . We add 1 at the end for the empty set. Hence our answer is f (3) + 1 = 678 .