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 nx x ··· x
1 2 nx ∈ { 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 nx x ··· x
1 2 nx ∈ { 3 , 4 } for all i . In terms of n , what is f (5 , 5 , . . . , 5)?
1 i
Answer: Let f ( x , x , . . . , x ) denote the n -variable version of the function. We will proven n 1 2 nthat f (5 , . . . , 5) = by induction. The base case was done in the two previous problems. Suppose 16
n nwe know that f (5 , 5 , . . . , 5) = . Let g ( x , . . . , x ) = 3 f ( x , . . . , x , 3). We have that g is 16
n − 1 n − 1 1 n − 1 n 1 n − 1
· 6
linear in x , . . . , x and g ( x , . . . , x ) = for all x , . . . , x ∈ { 3 , 4 } . By the inductive 1
1 n − 1 1 n − 1 1 n − 1
x ··· x
1 n − 1
f (5 ,..., 5)
n − 11
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) = .
4 nf (5 , 5 , . . . , 5 , 5) = 2 f (5 , 5 , . . . , 5 , 4) − f (5 , 5 , . . . , 5 , 3)
n n n
1 1 = f (5 , 5 , . . . , 5) − fn − 1 n − 1
2 3 = f (5 , 5 , . . . , 5)1
n − 1 =16
n − 1
6 · 6 = ,1
6 nand this proves our conjecture by induction.
Team Round