HMMT 十一月 2015 · 冲刺赛 · 第 18 题

HMMT November 2015 — Guts Round — Problem 18

[ 10 ] A function f satisfies, for all nonnegative integers x and y : • f (0 , x ) = f ( x, 0) = x • If x ≥ y ≥ 0, f ( x, y ) = f ( x − y, y ) + 1 • If y ≥ x ≥ 0, f ( x, y ) = f ( x, y − x ) + 1 Find the maximum value of f over 0 ≤ x, y ≤ 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2015, November 14, 2015 — GUTS ROUND Organization Team Team ID#

解析

[ 10 ] A function f satisfies, for all nonnegative integers x and y : • f (0 , x ) = f ( x, 0) = x • If x ≥ y ≥ 0, f ( x, y ) = f ( x − y, y ) + 1 • If y ≥ x ≥ 0, f ( x, y ) = f ( x, y − x ) + 1 Find the maximum value of f over 0 ≤ x, y ≤ 100. Proposed by: Alexander Katz Answer: 101 Firstly, f (100 , 100) = 101. To see this is maximal, note that f ( x, y ) ≤ max { x, y } + 1, say by induction on x + y .