1
$\begingroup$

Let $f$ be a bijective (one-one and onto) function from the set $$A=\{1,2,3,…,n\}$$ to itself. Show that there is a positive integer $M>1$ such that $$f^M(i)=f(i)$$ for each $i\in A$

[$f^M$ denotes the composite function $f\times f \times f \times \dotsb \times f$, repeated $M$ times.]

Please help me!!!

$\endgroup$
3
  • $\begingroup$ Have you seen some group theory? $\endgroup$ Dec 18 '16 at 9:19
  • $\begingroup$ no but I mean $f^M(i)=f(i) $\endgroup$ Dec 18 '16 at 9:20
  • 1
    $\begingroup$ Yes it is obvious $\endgroup$ Dec 18 '16 at 9:26
3
$\begingroup$

Consider the set $S$ to be the set of all bijective functions on $A$. Then check that $|S| = n!$. In fact, all you need is that $|S| < \infty$.

Now consider the set $T:= \{f, f^2, f^3, \ldots\} \subset S$. Since $T$ is finite, $\exists n,m\in \mathbb{N}$ such that $n\neq m$ and $$ f^n = f^m $$ as functions (ie. $f^n(i) = f^m(i)$ for all $1\leq i\leq m$).

Can you use this to construct the number $M$ you need?

$\endgroup$
1
$\begingroup$

Hint: Look at $1,f(1),f^2(1),\ldots$. This is a repeating sequence of some length. Look at all other such sequences and their lengths. Let $N$ be the product of all those lengths. What is $f^N(i)$? What is $f^{N+1}(i)$?

$\endgroup$
0
$\begingroup$

Obviously $f \in S_n$, the symmetric group on sets of $n$ elements, which is finite. Then there must be a positive integer $M$ with $f^M = e$, where $e$ is the (multiplicative) identity, otherwise $f$ would generate an infinite set.

In other words at some finite $j$ we must have a repetition of some prior element at $i$, $i < j$: $$ f^j = f^i \iff f^{j-i} = e $$ so $M = j - i > 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.