HMMT 二月 2010 · COMB 赛 · 第 3 题
HMMT February 2010 — COMB Round — Problem 3
题目详情
英文原题
- [ 4 ] How many ways are there to choose 2010 functions f , . . . , f from { 0 , 1 } to { 0 , 1 } such that
1 2010
f ° f ° · · · ° f is constant? Note: a function g is constant if g ( a ) = g ( b ) for all a, b in the domain
2010 2009 1
of g .
解析
英文解析
- [ 4 ] How many ways are there to choose 2010 functions f , . . . , f from { 0 , 1 } to { 0 , 1 } such that
1 2010
f ° f ° · · · ° f is constant? Note: a function g is constant if g ( a ) = g ( b ) for all a, b in the domain
2010 2009 1
of g .
2010 2010 1
Answer: 4 − 2 If all 2010 functions are bijective , then the composition f ° f ° · · · ° f
2010 2009 1
will be bijective also, and therefore not constant. If, however, one of f , . . . , f is not bijective, say
1 2010
f , then f (0) = f (1) = q , so f ° f ° · · · ° f ° f ° · · · f (0) = f ° f ° · · · ° f ( q ) =
k k k 2010 2009 k +1 k 1 2010 2009 k +1
f ° f ° · · · ° f ° f ° · · · f (1). So the composition will be constant unless all f are bijective.
2010 2009 k +1 k 1 i
Since there are 4 possible functions from { 0 , 1 } to { 0 , 1 } and 2 of them are bijective, we subtract the 2
2010 2010
cases where all the functions are bijective from the total to get 4 − 2 .