At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
Given a real number x, and a natural number N>1. Consider the numbers : 0,x−⌊x⌋,2x−⌊2x⌋,…,Nx−⌊Nx⌋. Show that some pair of these numbers differs by at most 1/N.
Use the pigeon-hole principle
But what do they want from me? What should I proof?
Prove that there exists a pair of numbers such that the difference between them is less or equal to than 1/N
oh ok thank you :D now I understand.. i'll think about it.. but how can the pigeon-hole principle help me?
I guess it is not exactly the pigeon-hole principle
The idea is to prove that the total distance between the numbers is greater than 1
no, the distance between the 2 numbers can't be greater than 1/N
Sorry, I meant to say that if the distance between all of the numbers is greater than 1/N, then the total distance is greater than 1. This is a contradiction, so there has to exist a pair of numbers with distance less than 1/N.
Why it is a contradiction?
\[0 \le x-\lfloor x \rfloor < 1\]
So all of the numbers are contained in an interval of length 1
Sorry but do you believe that I still can't get your point? what do you mean by "total distance" ?
Yeah, that is a bit ambiguous
why the total difference should be less than 1?
So if we suppose that all of the points are at a distance greater than 1/N from each other, 2 adjacent points on the number line must be separated by at least 1/N
Let's call P_0 the smallest point, P_1 the next largest, P_2 the next largest, et c.
The distance between point P_n and point P_n+x must be greater than x/N
The total distance is the distance between P_0 and P_N
This distance is clearly greater than 1
P_0 is 0
Therefore, P_N is greater than 1
This is a contradiction, as: \[x - \lfloor x \rfloor < 1\]
Therefore, our initial assumption, that the distance between any adjacent points is greater than 1/N, must be false
And that is the proof.
Thank you very much :D
You are welcome