Combination of Functions

Probability Level 4

Let a function $f$ be defined as $f: \{1,2,3,4\} \to \{1,2,3,4\}$ .

If $f$ satisfies $f(f(x)) = f(x)$ for all $x\in \{1,2,3,4\}$ , then the number of such functions $M$ and the probability of selecting a bijective function is $N$ .

Given that $M +N$ can be expressed as $\dfrac PQ$ , where $P$ and $Q$ are coprime positive integers, find $P \bmod Q$ .

The answer is 1.

2 solutions

Guillermo Templado
Dec 28, 2016

The only bijective function $f: A = \{1,2,3,4\} \to A =\{1,2,3,4\}$ such that $f(f(x) = f(x), \space \forall x \in A$ is the identity function in $A$ , ( $f = Id_A$ ) ,because if $f \neq Id_A$ then $\exists x \in A$ such that $f(x) \neq x$ and then $f(f(x)) = f(x) \Rightarrow$ that function is not bijective. So $N = \frac{1}{M} \Rightarrow M + N = \frac{M^2 + 1}{M} = \frac{P}{Q}$ due to $\text{ gcd (}M^2 + 1, M) = 1$ because $-M \cdot M + M^2 +1 = 1$ and hence $P \bmod Q = 1$

Note .- $M \neq 1$

I arrived at the answer that M = 29 and N = 1/29 . Can anyone verify whether it is correct or wrong .

Arghyadeep Chatterjee - 2 years, 7 months ago

My answer was M = 41 and N = 1/41. I separated the problem into cases in which the functions mapped onto 1, 2, 3 and 4 elements in the image, using the fact that any number in the image that had a different number mapping to it required that the function would map that number to itself and then found the number of functions in each case using permutations and the product rule. I think my answer is correct but I'm not 100% sure. These kinds of questions that demand ambiguous answers bother me.

Tristan Goodman - 3 weeks, 2 days ago

Arghyadeep Chatterjee
Nov 4, 2018

I arrived at the answer that M = 29 and N = 1/29 . Can anyone verify whether it is correct or wrong

Combination of Functions

The answer is 1.

2 solutions

0 pending reports