2013 AIME II Problem 11

Question

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.

Answer

Answer: 399

Concepts:function combinations casework

Difficulty rating: 2890

Small hint:

If

f(f(x)) = a

always, let

S

be the set of elements that

f

sends to

a.

Show

f(a) = a

and every element outside

S

maps into

S \setminus \{a\}

Big hint:

With

|S| = k:

choose

a,

choose the rest of

S,

then send each of the

7 - k

outside elements anywhere in

S \setminus \{a\},

and sum over

k

Solution:

Say

f(f(x)) = a

for all

x,

and let

S = \{x : f(x) = a\}.

Picking any

t \in S,

we get

a = f(f(t)) = f(a),

so

a \in S.

Every

x

satisfies

f(x) \in S

(because

f(f(x)) = a

), and if

x \notin S

then

f(x) \ne a,

so

f

maps the complement of

S

into

S \setminus \{a\}.

Conversely, any

f

built this way works.

If

|S| = k,

we choose the constant

a

in

7

ways, the remaining

k - 1

elements of

S

in

\binom{6}{k-1}

ways, and an image in

S \setminus \{a\}

for each of the

7 - k

other elements in

(k-1)^{7-k}

ways. Hence

\begin{aligned} N &= \scriptsize 7\sum_{k=1}^{7} \binom{6}{k-1}(k-1)^{7-k} \\ &\scriptsize = 7\,(0 + 6 + 240 + 540 + 240 + 30 + 1) \\ &= 7 \cdot 1057 = 7399. \end{aligned}

The remainder when

N