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 2 Since there are 4 possible functions from { 0 , 1 } to { 0 , 1 } and 2 of them are bijective, we subtract the 2010 2010 cases where all the functions are bijective from the total to get 4 − 2 .