HMMT 十一月 2021 · 冲刺赛 · 第 30 题

HMMT November 2021 — Guts Round — Problem 30

[15] The function f : Z → Z satisfies • f ( x, 0) = f (0 , y ) = 0, and • f ( x, y ) = f ( x − 1 , y ) + f ( x, y − 1) + x + y for all nonnegative integers x and y . Find f (6 , 12). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2021, November 13, 2021 — GUTS ROUND Organization Team Team ID#

解析

[15] The function f : Z → Z satisfies • f ( x, 0) = f (0 , y ) = 0, and • f ( x, y ) = f ( x − 1 , y ) + f ( x, y − 1) + x + y for all nonnegative integers x and y . Find f (6 , 12). Proposed by: Joseph Heerens Answer: 77500 ( ) x + y +2 Solution: We claim f ( x, y ) = − ( x + y + 2). Indeed, the hypothesis holds true for our base x +1 cases f ( x, 0) and f (0 , y ), and moreover, ( ) ( ) ( ) x + y + 1 x + y + 1 x + y + 2 f ( x − 1 , y )+ f ( x, y − 1)+ x + y = + − 2( x + y +1)+ x + y = − ( x + y +2) . x x + 1 x + 1 ( ) 20 Thus, the final answer is − 20 = 77500. 7 Here is a way to derive this formula from scratch. The idea is that the second condition harks back to the Pascal’s triangle rule, sans some modifications. Write f ( x, y ) = g ( x, y ) − x − y , so then g (0 , t ) = g ( t, 0) = t and g ( x, y ) = g ( x − 1 , y ) + g ( x, y − 1) + 2. Then, letting g ( x, y ) = h ( x, y ) − 2 gives h ( x, y ) = h ( x − 1 , y ) + h ( x, y − 1), which is exactly Pascal’s rule. We are given the base cases ( ) x + y +2 h (0 , t ) = h ( t, 0) = t + 2, which is starting “inside” of Pascal’s triangle, so h ( x, y ) = . x +1