Programmer solving math problems about grasshoppers

Being a software engineer who has been and still is working at the biggest tech companies in the world I was always curious about the engineers working on the other side of the fence. The group I knew very little about, except for the crazy salaries they earn working in the finance industry. So I was speaking to a current colleague of mine the other day and he shared one of the interview questions asked by one of the famous trading companies, which extensively hires engineers for non-engineering positions. I would like to share the asked question and present a solution, which I found particularly interesting.

Problem:

A grasshopper jumps along the circle of length 1 (circumference) in a clockwise direction. It starts at point 0 and every jump is of the same length j where j is an irrational number (number which cannot be represented as a result of division of two integer numbers). Prove that the grasshopper will visit every single segment present on the circle.

Solution:

We will say that the grasshopper has visited point x if it arrived at the point x units away from the starting point 0 in a clockwise direction as a result of his jump.

Lemma A: For any segment on the circle of length L if the grasshopper has visited point x < L then it will visit that segment as well.
Indeed, imagine that after n number of jumps, the grasshopper visited point x < L , so after n jumps it might have traveled few times around the circle, so he covered a distance equal m + x where is m is some integer number. So after 2*n jumps he will travel 2*m + 2*x distance, but given that the circumference of the circle is 1 the grasshopper will end up at point 2*x . So after n, 2*n, 3*n,… it will be visiting all the points: x, 2*x, 3*x, ... , and at some point it will visit that aforementioned segment (this is nearly obvious, just pick a maximum k such that k * x is before the segment start. Then (k+1)*x is inside that segment)

Now that the lemma A is proven, we can prove the problem statement itself.

Assume that the problem statement is false. That means there is some segment of length z somewhere on the circle, which cannot be visited by the grasshopper. But due to lemma A it means that grasshopper can never visit a point x such that x < z . (Otherwise we would visit that segment). It is equivalent to saying that {j*n} > z for any natural number n , where {} is a fractional part. (B)

Now we will use the fact that j is an irrational number. For any irrational number, there is a rational number a/b where both a and b are integers, such that a/b < j and j < (a+1)/b . As we established above in statement B:

j - a/b > z/b

To understand why it is equivalent to statement B multiply both sides of the inequality by b

Let’s pick some rational number x/y such that x/y <= z . That means,

j > a/b + z/b >= a/b + x/(y*b) >= a/b + 1/(y*b) = (a*y + 1)/(b*y)

So there is some fixed integer y, such that if j > a/b then j > (a*y+1)/b*y
If we denote a = a*y+1 and b = b*y and reapply the same logic, that would mean that:

j > ((a*y+1)*y +1)/b*y*y = (y^2*a + y + 1)/(b*y^2) 

If we keep applying the same formula:

j > (y^n*a)/(y^n*b) + (y^(n-1)+...+1)/(y^n*b) = a/b + 1/b(y-1) - 1/(y-1)*y^n*b

Obviously we can pick a really big value of n so that the last term is almost zero, which means that:

j > a/b + 1/b*(y-1) 

(the sign is strictly greater because j is irrational)

So if j > a/b + 1/y*b then j > a/b + 1/b*(y-1) . Therefore we can keep decreasing the value of y until we y is more than 1. Therefore:

j > a/b + 1/b = (a+1)/b

Which contradicts our assumption that j < (a+1)/b . So our initial assumption was wrong, and the problem statement is correct.

Please comment