HMMT 十一月 2010 · 团队赛 · 第 10 题

HMMT November 2010 — Team Round — Problem 10

[ 6 ] A function f ( x , x , . . . , x ) is linear in each of the x and f ( x , x , . . . , x ) = when 1 2 n i 1 2 n x x ··· x 1 2 n x ∈ { 3 , 4 } for all i . In terms of n , what is f (5 , 5 , . . . , 5)? i

解析

[ 6 ] A function f ( x , x , . . . , x ) is linear in each of the x and f ( x , x , . . . , x ) = when 1 2 n i 1 2 n x x ··· x 1 2 n x ∈ { 3 , 4 } for all i . In terms of n , what is f (5 , 5 , . . . , 5)? i 1 Answer: Let f ( x , x , . . . , x ) denote the n -variable version of the function. We will prove n n 1 2 n 6 1 that f (5 , . . . , 5) = by induction. The base case was done in the two previous problems. Suppose n n 6 1 we know that f (5 , 5 , . . . , 5) = . Let g ( x , . . . , x ) = 3 f ( x , . . . , x , 3). We have that g is n − 1 n − 1 1 n − 1 n 1 n − 1 · 6 1 linear in x , . . . , x and g ( x , . . . , x ) = for all x , . . . , x ∈ { 3 , 4 } . By the inductive 1 n − 1 1 n − 1 1 n − 1 x ··· x 1 n − 1 f (5 ,..., 5) 1 n − 1 hypothesis, we have g (5 , . . . , 5) = = f (5 , . . . , 5). Therefore, f (5 , . . . , 5 , 3) = . n − 1 n − 1 n 6 3 f (5 ,..., 5) n − 1 Similarly, f (5 , . . . , 5 , 4) = . n 4 f (5 , 5 , . . . , 5 , 5) = 2 f (5 , 5 , . . . , 5 , 4) − f (5 , 5 , . . . , 5 , 3) n n n 1 1 = f (5 , 5 , . . . , 5) − f n − 1 n − 1 2 3 1 = f (5 , 5 , . . . , 5) n − 1 6 1 = n − 1 6 · 6 1 = , n 6 and this proves our conjecture by induction. Team Round