1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeonhole problem?

  1. Oct 23, 2008 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations
    pigeonhole principle?

    3. The attempt at a solution
    The section is on counting and the pigeonhole principle. But I'm not sure how to start this one.
  2. jcsd
  3. Oct 23, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Pigeonhole problem?
  1. Pigeonhole problem set (Replies: 5)

  2. Pigeonhole principle (Replies: 12)

  3. Pigeonhole Principle (Replies: 1)