PUMaC 2014 · 代数（A 组） · 第 8 题

PUMaC 2014 — Algebra (Division A) — Problem 8

[ 8 ] For nonnegative integer n , the following are true: f (0) = 0 f (1) = 1 m ( m − 1) m ( m +1) m ( m − 1) m ( m +1) f ( n ) = f ( n − ) − f ( − n ) for integer m satisfying m ≥ 2 and < n ≤ . 2 2 2 2 Find the smallest n such that f ( n ) = 4. 1

解析

[ 8 ] For nonnegative integer n , the following are true: f (0) = 0 f (1) = 1 m ( m − 1) m ( m +1) m ( m − 1) f ( n ) = f ( n − ) − f ( − n ) for integer m satisfying m ≥ 2 and < n ≤ 2 2 2 m ( m +1) . 2 Find the smallest n such that f ( n ) = 4. Solution: m ( m − 1) If f ( n ) = f ( a ) f ( b ), then a + b = m (where a ≥ 1, b ≥ 0), and furthermore, n = + a = 2 ( a + b )( a + b − 1)

a (call this equality *). So, if a or b increases, then n increases. 2 f (0) = 0 , f (1) = 1 , f (2) = 0, and for n ≥ 3, it’s true that n > a, b, m . And a, b, m are uniquely determined by n . Let n be the smallest n that satisfies f ( n ) = k . n = 1. And f ( n ) = − 1 = 0 − 1 = f (2) − k 1 − 1 f (1), which means that from our identity *, it follows that n = 5. And f ( n ) = 1 − ( − 1) = − 1 2 f ( n ) − f ( n ) = f (1) − f (5), which gives us f ( n ) = 16. And f ( n ) = − 1 − 1 = f ( n ) − f (1), 1 − 1 2 − 2 − 1 which gives us n = 20. Continuing this process gives us n = 211 , n = 215 , n = 646. So, − 2 3 3 4 our answer is 646 . 3