# Homework Help: Larsen problem

1. Dec 31, 2007

### ehrenfest

[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. Dec 31, 2007

### 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?

3. Dec 31, 2007

### 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?

4. Dec 31, 2007

### Dick

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

5. Dec 31, 2007

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

6. Dec 31, 2007

### Dick

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