Not so many irreducible fractions

I accidently found few papers in my parents' house, dating since I was 15 (I have no idea how those papers survived almost 19 years, but I am glad I found them). Those days, I was involved in Mathematical Olympiads, at school and national level. As you can imagine, those papers contain problems :)

This post is dedicated to one particular problem, that is:

Prove that any arbitrary segment of size 1⁄n (n >1, n∈N) on ℜ contains no more than (n+1)⁄2 irreducible fractions of type p⁄q (p,q∈Z), where 1≤q≤n.

What I remember, so far, is that this problem was part of the Liouville numbers lesson. Unfortunately, I can't reproduce the lesson (I can't remember it :(), but ... below is an alternative proof, containing the sort of analysis I like to define as "Don't be lazy to unfold the details".

Let's pick up an arbitrary number α∈ℜ so that it defines the [α, α+1⁄n] segment. For any rational number (irreducible fraction) p⁄q (p,q∈Z, 1≤q≤n) on this segment we have:
α≤p⁄q≤α+1⁄n or
(*)

Now:

1. Let's consider q=1, then from (*) we have α≤p₁≤α+1⁄n. There can be maximum one such integer number p₁. Why? Let's suppose there exists another one t₁≠p₁ so that
α≤t₁≤α+1⁄n
But this means 1≤|t₁-p₁|≤1⁄n<1, which is impossible (absolute difference between 2 different integers is always ≥1).

2. Let's consider q=2, then from (*) we have 2⋅α≤p₂≤2⋅α+2⁄n. There can be maximum one such integer number p₂ (proof is identical to the case above except 1≤|t₂-p₂|≤2⁄n).

...

N-1. Let's consider q=n-1, then from (*) we have (n-1)⋅α≤p_n-1≤(n-1)⋅α+(n-1)⁄n. There can be maximum one such integer number p_n-1 (proof is identical to the case(s) above except 1≤|t_n-1-p_n-1|≤(n-1)⁄n).

N. Let's consider q=n, then from (*) we have n⋅α≤p≤n⋅α+1. There can be maximum two (!!!) such integer numbers p_n and p_n+1. Why? Imagine that n⋅α is an integer, then n⋅α+1 is another different integer. If n⋅α isn't an integer, then there will be maximum one integer satisfying n⋅α≤p_n≤n⋅α+1 (e.g. if we suppose there will be 2 integers n⋅α≤p_n<t≤n⋅α+1, then 1≤t–p_n≤1 ⇒ t=p_n+1. Also n⋅α+1 ≤p_n+1=t≤n⋅α+1 ⇒ p_n+1= n⋅α+1 ⇒ p_n= n⋅α so n⋅α is an integer).

At this step we know that there could be maximum (n+1) integers p_i, satisfying (*) where 1≤q≤n.

Next, let's consider all the even q between 1 and n-1, e.g. q=2⋅s, then we have from (*)

2⋅s⋅α≤p_2⋅s≤2⋅s⋅α+2⋅s⁄n and
s⋅α≤p_s≤s⋅α+s⁄n which is ⇔ (multiplying by 2)
2⋅s⋅α≤2⋅p_s≤2⋅s⋅α+2⋅s⁄n
from which we can see that:
|p_2⋅s-2⋅p_s|≤2⋅s⁄n=q⁄n<1 ⇒ p_2⋅s=2⋅p_s or
p_q⁄q=p_2⋅s⁄(2⋅s)=p_s⁄s or
p_q⁄q is reducible.

We can state now that for any even q, p_q⁄q is reducible, but there are (n-1)⁄2 even numbers between 1 and n-1. As a result we have maximum (n-1)⁄2 irreducible fractions satisfying:
α≤p⁄q≤α+1⁄n, where 1≤q≤n-1

What about the q=n case?

As we stated in the case N above, there can be maximum two integers (we noted then p_n and p_n+1) satisfying
n⋅α≤p≤n⋅α+1
if, and only if n⋅α is an integer.

If we consider p_n<p_n+1 then
n⋅α=p_n
n⋅α+1=p_n+1=p_n+1

From the case 1 above n⋅α≤n⋅p₁≤n⋅α+1 or p_n≤n⋅p₁≤p_n+1 which means
p_n=n⋅p₁ or
p_n+1=p_n+1=n⋅p₁

As a result, either p_n⁄n or p_n+1⁄n is further reducible, considering p₁ exists. So we can have maximum one irreducible fraction. This means total maximum is 1+(n-1)⁄2=(n+1)⁄2 now.

If p₁ doesn't exists (we stated there could be maximum 1), then both p_n⁄n and p_n+1⁄n can be irreducible, but the q=1 case (case 1) will have to be removed from the previously analysed options so 2-1+(n-1)⁄2=(n+1)⁄2.

One can observe that from the case 1, we can apply this technique (of multiplying) and deduce that p_i=i⋅p₁, 1≤i≤n-1. Yes, this is true, if we admit there exists p₁ at all (this part is very subtle). But even in this particular case, the total is 2 irreducible fractions that is less than (n+1)⁄2 anyway.