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!

Larsen problem

  1. Dec 31, 2007 #1
    [SOLVED] larsen problem

    1. The problem statement, all variables and given/known data
    Let X be any real number. Prove that among the numbers

    X,2X,3X,...,(n-1)X

    there is one that differs from an integer by at most 1/n.
    Use the pigeon-hole principle.
    2. Relevant equations



    3. The attempt at a solution
    There is probably a simple two-sentence solution to this problem--I just can't find it.

    So, the obvious candidates for the pigeons are the numbers X,2X,...,(n-1)X mod 1. But what are the pigeon holes? I want take the unit interval and divide it up into n subintervals of length 1/n and then say that 1 of the pigeons flies into either the first or the last interval. But that's not how the pigeon-hole principle works.

    I need to find n-1 bins of some sort such that two of the pigeons going into one bin implies that one of the those numbers mod 1 is less than 1/n or greater than n-1/n....

    Maybe I have the wrong pigeons. Maybe they should be the differences between consecutive numbers mod 1...
     
  2. jcsd
  3. Dec 31, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If two of your pigeons, say AX and BX (B>A), fly into one bin, what are the bin possibilities for (B-A)X?
     
  4. Dec 31, 2007 #3
    I see. So let the pigeons be numbers X,2X,...,(n-1)X mod 1. Let the pigeonholes be the [0,1/n],[1/n,2/n],...,[n-1/n,1].

    There are n pigeons and n pigeonholes, but if any of the numbers fly into the first or last bin, we are done. So, assume the first and last bins are empty. Then there are n pigeons and n-2 pigeonholes. Two pigeons AX and BX, (B>A) fly into some bin, which implies that (B-A)X must have flown into the first bin, a contradiction.

    Is that right?
     
  5. Dec 31, 2007 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Basically. I would say (B-A)X could wind up in either the first or the last bin. We are working mod 1.
     
  6. Dec 31, 2007 #5
    I would say that (A-B)X is in the last bin and (B-A)X is in the first bin.

    (B-A)X = BX-AX = something less than 1/n mod 1
     
  7. Dec 31, 2007 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    n=4. X=.9. (2-1)X mod 1=.9. Last bin. X=1.1. (2-1)X mod 1=.1. First bin.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Larsen problem
  1. A problem (Replies: 2)

  2. Larsen problem (Replies: 7)

  3. Larsen problem (Replies: 11)

  4. Larsen problem (Replies: 5)

  5. Problem - (Replies: 7)

Loading...