Question

Consider the set A = {1, 2, 3, 4, 5}. Let the number of functions defined from A to A for which f(f(i)) = i for at least one i ∈ A is N then

• A. N has four divisors
• B. N is odd
• C. N is even
• D. N is of the form 4$\lambda$ + 1 (where $\lambda$ ∈ N)

Answer 1

Answer: (A), (B), (D)

(A), (B) and (D)

Answer 2

We are given

$A=\{1,2,3,4,5\},\quad \text{and } f:A\to A$

with the condition that

$f(f(i))=i \quad \text{for at least one } i\in A.$

A key observation is that for any $i\in A,\; f(f(i))=i$ holds if either

1. $f(i)=i$ (i.e. $i$ is a fixed point), or

2. There exists $j\neq i$ such that $f(i)=j$ and $f(j)=i$ (i.e. $i$ is part of a 2‐cycle).

Thus “having at least one $i$ with $f(f(i))=i$” is equivalent to saying that the function $f$ has at least one fixed point or a 2‐cycle.

Now note that if a function has a fixed point (at least one $i$ with $f(i)=i$) then automatically $f(f(i))=f(i)=i$. Hence the only functions that do not satisfy “$f(f(i))=i$ for some $i$” are exactly the functions that have

(i) no fixed point (i.e. $f(i)\neq i$ for all $i$), and (ii) no 2‐cycle (i.e. there are no distinct $i,j$ with $f(i)=j$ and $f(j)=i$).

Call such functions “complement functions.”

Step 1. Total number of functions from $A$ to $A$ is

$5^5=3125.$

Step 2. Count the complement functions. Notice that if a function has no fixed point then for every $i\in A$ we must choose $f(i)$ from the 4 elements of $A\setminus\{i\}$; if there were no further restriction, there would be $4^5=1024$ functions. However, among these some functions have a 2‐cycle.

Let $B_{ij}=\{f: f(i)=j \text{ and } f(j)=i\}$ for $i\neq j$. For a fixed pair $(i,j)$,

• We must have $f(i)=j$ and $f(j)=i$ (no worry about fixed point since $i\neq j$).

• For the remaining $5-2=3$ elements, each can be assigned arbitrarily (each with 5 possibilities) if there were no “no–fixed–point” condition but here we are already in the world of functions with no fixed point so for every remaining $k$ we must have $f(k)\neq k$; that gives 4 choices for each.

Thus $|B_{ij}|=4^3=64.$

There are $\binom{5}{2}=10$ distinct pairs. Also, note that if two 2‐cycles are “disjoint” (which is the only possibility for two 2‐cycles to occur in a fixed–point–free function on 5 elements), then for each such pair the remaining element (only one left) has 4 choices. The number of ways to choose 2 disjoint pairs from 5 elements is

$\frac{\binom{5}{2}\binom{3}{2}}{2!}=15.$

By the inclusion–exclusion principle the number of functions with no fixed point and no 2–cycle is:

$\text{No–FP \& no 2-cycle} =4^5-\binom{5}{2}\,4^3+15\cdot4^1.$

That is:

$1024-10\cdot 64+15\cdot 4 =1024-640+60=444.$

Thus the number of functions $f:A\to A$ for which there is at least one $i$ with $f(f(i))= i$ is

$N =3125-444=2681.$

Step 3. Now we check the given options.

(A) “$N$ has four divisors.” Write $2681=7\times 383.$ (One may check that 383 is prime.) Hence the divisors are $1, 7, 383, 2681$; exactly 4 divisors. ✓

(B) “$N$ is odd.” Since 2681 is odd. ✓

(C) “$N$ is even.” False.

(D) “$N$ is of the form $4\lambda+1$” Indeed, $2681\equiv 1 \pmod{4}$ (since $2681-4\times670=1$). ✓

Thus the correct options are (A), (B) and (D).

Explanation (minimal): Total functions $=5^5=3125$. A function has $f(f(i))=i$ for some $i$ if it has a fixed point or a 2-cycle. The complement functions (with no fixed point and no 2-cycle) are counted among FP–free functions (4⁵=1024) by excluding those having at least one 2-cycle via inclusion–exclusion:

No–FP & no 2-cycle = 1024 – 10·64 + 15·4 = 444. Thus, $N=3125-444=2681$. Since $2681=7\times383$, it has exactly 4 divisors, is odd, and $2681\equiv1\pmod{4}$.