Problem:
Let A={1,2,3,4,5,6,7}, and let N be the number of functions f from set A to set A such that f(f(x)) is a constant function. Find the remainder when N is divided by 1000.
Solution:
Suppose that f is a function from A to A such that f(f(x)) is constant. Let a∈A be the constant value of f(f(x)). Suppose that S={x∈A∣f(x)=a} has k elements. Note that a∈S, and for x∈/S, f(x)∈S−{a}. It follows that one can choose such a function f by selecting a in one of 7 ways, selecting the other elements of S in (k−16) ways, and selecting values for f(x) for each x∈/S in (k−1)7−k ways. Thus the number of functions is
k=1∑77⋅(k−16)⋅(k−1)7−k=0+7⋅6+7⋅240+7⋅540+7⋅240+7⋅30+7⋅1=7⋅1057
The requested remainder is then 7⋅57=399.
The problems on this page are the property of the MAA's American Mathematics Competitions