HMMT 二月 2010 · GEN1 赛 · 第 4 题

HMMT February 2010 — GEN1 Round — Problem 4

[ 4 ] Let S = 0 and let S equal a + 2 a + . . . + ka for k ≥ 1. Define a to be 1 if S < i and -1 if 0 k 1 2 k i i − 1 S ≥ i . What is the largest k ≤ 2010 such that S = 0? i − 1 k

解析

[ 4 ] Let S = 0 and let S equal a + 2 a + . . . + ka for k ≥ 1. Define a to be 1 if S < i and -1 if 0 k 1 2 k i i − 1 S ≥ i . What is the largest k ≤ 2010 such that S = 0? i − 1 k Answer: 1092 Suppose that S = 0 for some N ≥ 0. Then a = 1 because N + 1 ≥ S . The N N +1 N following table lists the values of a and S for a few k ≥ N : k k k a S k k N 0 N + 1 1 N + 1 N + 2 1 2 N + 3 N + 3 − 1 N N + 4 1 2 N + 4 N + 5 − 1 N − 1 N + 6 1 2 N + 5 N + 7 − 1 N − 2 We see inductively that, for every i ≥ 1, S = 2 N + 2 + i N +2 i and S = N + 1 − i N +1+2 i thus S = 0 is the next k for which S = 0. The values of k for which S = 0 satisfy the recurrence 3 N +3 k k relation p = 3 p +3, and we compute that the first terms of the sequence are 0 , 3 , 12 , 39 , 120 , 363 , 1092; n +1 n hence 1092 is our answer.