1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook