Solving the Larsen Problem with Pigeon-Hole Principle

[ehrenfest]

[SOLVED] larsen problem

Homework Statement

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.

Homework Equations

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

 

[Dick]

If two of your pigeons, say AX and BX (B>A), fly into one bin, what are the bin possibilities for (B-A)X?

 

[ehrenfest]

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?

 

[Dick]

Basically. I would say (B-A)X could wind up in either the first or the last bin. We are working mod 1.

 

[ehrenfest]

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

 

[Dick]

n=4. X=.9. (2-1)X mod 1=.9. Last bin. X=1.1. (2-1)X mod 1=.1. First bin.