HMMT 十一月 2024 · GEN 赛 · 第 5 题

HMMT November 2024 — GEN Round — Problem 5

Let f be a function on nonnegative integers such that f (0) = 0 and f (3 n + 2) = f (3 n + 1) = f (3 n ) + 1 = 3 f ( n ) + 1 for all integers n ≥ 0 . Compute the sum of all nonnegative integers m such that f ( m ) = 13 .

解析

Let f be a function on nonnegative integers such that f (0) = 0 and f (3 n + 2) = f (3 n + 1) = f (3 n ) + 1 = 3 f ( n ) + 1 for all integers n ≥ 0. Compute the sum of all nonnegative integers m such that f ( m ) = 13. Proposed by: Carlos Rodriguez Answer: 156 Solution: Let x denote the number x in base k . Observe that if f ( x ) = y , then k 3 3 f ( x 0 ) = f (3 x ) = 3 f ( x ) = y 0 3 3 and f ( x 1 ) = f ( x 2 ) = 3 f ( x ) + 1 = y 1 . 3 3 3 Thus, f ( n ) is simply n with all 2’s replaced with 1’s. We also see that 13 = 111 . Thus, f ( m ) = 13 if 3 3 3 and only if m = abc for digits a, b, c ∈ { 1 , 2 } . Each of a , b , and c takes on each possible value exactly 3 4 times, so the sum is 2 1 0 (4 · 1 + 4 · 2)(3 + 3 + 3 ) = 156 .