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}≤α+1⁄n*. There can be maximum one such integer number

*p*. Why? Let's suppose there exists another one

_{1}*t*so that

_{1}≠p_{1}*α≤t*

_{1}≤α+1⁄nBut this means

*1≤|t*, which is impossible (absolute difference between 2 different integers is always ≥1).

_{1}-p_{1}|≤1⁄n<1**2.** Let's consider *q=2*, then from **(*)** we have *2⋅α≤p _{2}≤2⋅α+2⁄n*. There can be maximum one such integer number

*p*(proof is identical to the case above except

_{2}*1≤|t*).

_{2}-p_{2}|≤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*(proof is identical to the case(s) above except 1≤|t

_{n-1}_{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*. Why? Imagine that

_{n+1}*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*(e.g. if we suppose there will be 2 integers

_{n}≤n⋅α+1*n⋅α≤p*, then

_{n}<t≤n⋅α+1*1≤t–p*⇒

_{n}≤1*t=p*. Also

_{n}+1*n⋅α+1 ≤p*⇒

_{n}+1=t≤n⋅α+1*p*⇒

_{n}+1= n⋅α+1*p*so

_{n}= n⋅α*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*which is ⇔ (multiplying by 2)

_{s}≤s⋅α+s⁄n*2⋅s⋅α≤2⋅p*

_{s}≤2⋅s⋅α+2⋅s⁄nfrom which we can see that:

*|p*⇒

_{2⋅s}-2⋅p_{s}|≤2⋅s⁄n=q⁄n<1*p*or

_{2⋅s}=2⋅p_{s}*p*or

_{q}⁄q=p_{2⋅s}⁄(2⋅s)=p_{s}⁄s*p*is reducible.

_{q}⁄qWe 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*) satisfying

_{n+1}*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}+1From the **case 1** above *n⋅α≤n⋅p _{1}≤n⋅α+1* or

*p*which means

_{n}≤n⋅p_{1}≤p_{n}+1*p*or

_{n}=n⋅p_{1}*p*

_{n+1}=p_{n}+1=n⋅p_{1}As a result, either *p _{n}⁄n* or

*p*is further reducible, considering

_{n+1}⁄n*p*exists. So we can have maximum one irreducible fraction. This means total maximum is

_{1}*1+(n-1)⁄2=(n+1)⁄2*now.

If *p _{1}* doesn't exists (we stated there could be maximum 1), then both

*p*and

_{n}⁄n*p*can be irreducible, but the

_{n+1}⁄n*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}*,

*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

_{1}*(n+1)⁄2*anyway.