返回题库

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

HMMT November 2015 — Guts Round — Problem 18

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [ 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.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HMMT November 2015, November 14, 2015 — GUTS ROUND
Organization Team Team ID#

解析

英文解析

  1. [ 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 .