2
$\begingroup$

Let $f$ be a one-to-one function from $X=\{1,2,\dots,n\}$ onto $X$. Let $f^k=f\circ f\circ \cdots \circ f$ denote the $k$-fold composition of $f$ with itself.

  1. Show that there are distinct positive integers $i$ and $j$ such that $f^i(x)=f^j(x)$ for all $x\in X$.
  2. Show that for some positive integer $k,~~~f^k(x)=x$ for all $x\in X$.
$\endgroup$
4
  • 1
    $\begingroup$ I feel like I'm reading a textbook ... $\endgroup$
    – Amitesh Datta
    Jul 23 '13 at 17:05
  • 1
    $\begingroup$ Tell us what you know and what you can use. $\endgroup$
    – lhf
    Jul 23 '13 at 17:10
  • $\begingroup$ I'd like to show this using something different than what this textbook requires. $\endgroup$
    – Marble Klaxon
    Jul 23 '13 at 17:17
  • $\begingroup$ I think the $f^i(x)=f^j(x)$ equality is throwing me off. $\endgroup$
    – Marble Klaxon
    Jul 23 '13 at 17:21
5
$\begingroup$

Hint: the powers $f^k$, like $f$, are all bijections of the finite set $X$ into itself, so they are essentially just permutations of the elements of $X$. In fact, they form a subgroup of the finite group of all permutations of $X$. (Hmmm... :) )

Apply the pigeon-hole principle. There are only finitely many bijections... how could the infinitely many powers of $f$ all be distinct?

$\endgroup$
2
  • $\begingroup$ Powers? What do you mean "powers"? $\endgroup$
    – Trancot
    Jul 23 '13 at 23:15
  • $\begingroup$ @Trancot $\{f^k\mid k\in \Bbb N\}$ $\endgroup$
    – rschwieb
    Jul 24 '13 at 1:36
1
$\begingroup$

If you can use group theory, then this is clear because $f$ has finite order in the symmetric group $S_n$.

$\endgroup$
5
  • $\begingroup$ Ooo! What does that mean? Maybe you could explain in detail. I'd like to learn. $\endgroup$
    – Marble Klaxon
    Jul 23 '13 at 16:57
  • $\begingroup$ @MarbleKlaxon I think one could argue he gave precisely the amount of detail you need to start learning and much more detail would be robbing you of learning. $\endgroup$
    – rschwieb
    Jul 23 '13 at 17:05
  • $\begingroup$ @rschwieb If the details are hidden in a language he/she doesn't speak then he cannot complete the idea. The language of the problem is simpler than the names "finite order", "symmetric group", and "group theory". And the solution doesn't really require those terms. $\endgroup$
    – OR.
    Jul 23 '13 at 17:22
  • $\begingroup$ @RGB I certainly agree with you, but I was speaking more towards the feeling floating around that the OP is just fishing for a complete answer. I could, of course, be completely wrong, and that would make me glad. $\endgroup$
    – rschwieb
    Jul 23 '13 at 20:25
  • $\begingroup$ No, "just enough" would be nice. To struggle is to learn... Well, sometimes. $\endgroup$
    – Trancot
    Jul 23 '13 at 22:31

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