Solving the Pigeonhole Problem with f(x) for n Elements

[endeavor]

Homework Statement

Let f be a one-to-one function from X = {1,2,...n} onto X. Let f ^k = f(f(f(...f(x))) be the k-fold composition of f with itself. Show that there are distinct positive integers i and j such that f ⁱ (x) = f ^j (x) for all x in X.

Homework Equations

pigeonhole principle?

The Attempt at a Solution

The section is on counting and the pigeonhole principle. But I'm not sure how to start this one.

 

[Dick]

Pigeonhole principle, yes. There are only a finite number of possible functions from X->X, yes? There are an infinite number of k's in the set of functions {f^k} for all k. That's a finite number of pigeonholes for an infinite number of k's. Two of the k's must be the same function.