HMMT 二月 2021 · 冲刺赛 · 第 16 题

HMMT February 2021 — Guts Round — Problem 16

[11] Let f : Z → Z be a function such that, for all positive integers a and b ,   b if a > b  f ( a, b ) = f (2 a, b ) if a ≤ b and f (2 a, b ) < a   f (2 a, b ) − a otherwise . 2021 Compute f (1000 , 3 ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT Spring 2021, March 06, 2021 — GUTS ROUND Organization Team Team ID#

解析

[11] Let f : Z → Z be a function such that, for all positive integers a and b ,   b if a > b  f ( a, b ) = f (2 a, b ) if a ≤ b and f (2 a, b ) < a   f (2 a, b ) − a otherwise . 2021 Compute f (1000 , 3 ). Proposed by: Akash Das Answer: 203 Solution: Note that f ( a, b ) is the remainder of b when divided by a . If a > b then f ( a, b ) is exactly b n mod a . If instead a ≤ b , our ”algorithm” doubles our a by n times until we have a × 2 > b . At this 2 n − 1 n point, we subtract a from f ( a · 2 , b ) and iterate back down until we get a > b − a · k > 0 and f ( a, b ) = b − a · k for some positive integer k . This expression is equivalent to b − a · k mod a , or b mod a . 2021 Thus, we want to compute 3 mod 1000. This is equal to 3 mod 8 and 78 mod 125. By CRT, this implies that the answer is 203.