HMMT 十一月 2013 · GEN 赛 · 第 10 题

HMMT November 2013 — GEN Round — Problem 10

[ 8 ] How many functions f : { 1 , 2 , . . . , 2013 } → { 1 , 2 , . . . , 2013 } satisfy f ( j ) < f ( i )+ j − i for all integers i, j such that 1 ≤ i < j ≤ 2013?

解析

[ 8 ] How many functions f : { 1 , 2 , . . . , 2013 } → { 1 , 2 , . . . , 2013 } satisfy f ( j ) < f ( i )+ j − i for all integers i, j such that 1 ≤ i < j ≤ 2013? ( ) 4025 Answer: Note that the given condition is equivalent to f ( j ) − j < f ( i ) − i for all 2013 1 ≤ i < j ≤ 2013. Let g ( i ) = f ( i ) − i , so that the condition becomes g ( j ) < g ( i ) for i < j and 1 − i ≤ g ( i ) ≤ 2013 − i . However, since g is decreasing, we see by induction that g ( i + 1) is in the desired range so long as g ( i ) is in the desired range. Hence, it suffices to choose 2013 values for ( ) 4025 g (1) , . . . , g (2013) in decreasing order from [ − 2012 , 2012], for a total of possible functions. 2013