Pigeonhole problem?

  • Thread starter endeavor
  • Start date
  • #1
176
0

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 i (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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
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.
 

Related Threads on Pigeonhole problem?

  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
5
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
Replies
5
Views
1K
  • Last Post
Replies
8
Views
760
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
12
Views
10K
  • Last Post
Replies
3
Views
1K
Top