Sunday, October 23, 2011

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 α≤p1≤α+1⁄n. There can be maximum one such integer number p1. Why? Let's suppose there exists another one t1≠p1 so that
α≤t1≤α+1⁄n
But this means 1≤|t1-p1|≤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⋅α≤p2≤2⋅α+2⁄n. There can be maximum one such integer number p2 (proof is identical to the case above except 1≤|t2-p2|≤2⁄n).

...

N-1. Let's consider q=n-1, then from (*) we have (n-1)⋅α≤pn-1≤(n-1)⋅α+(n-1)⁄n. There can be maximum one such integer number pn-1 (proof is identical to the case(s) above except 1≤|tn-1-pn-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 pn and pn+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⋅α≤pn≤n⋅α+1 (e.g. if we suppose there will be 2 integers n⋅α≤pn<t≤n⋅α+1, then 1≤t–pn≤1t=pn+1. Also n⋅α+1 ≤pn+1=t≤n⋅α+1pn+1= n⋅α+1pn= n⋅α so n⋅α is an integer).

At this step we know that there could be maximum (n+1) integers pi, 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⋅α≤p2⋅s≤2⋅s⋅α+2⋅s⁄n and
s⋅α≤ps≤s⋅α+s⁄n which is ⇔ (multiplying by 2)
2⋅s⋅α≤2⋅ps≤2⋅s⋅α+2⋅s⁄n
from which we can see that:
|p2⋅s-2⋅ps|≤2⋅s⁄n=q⁄n<1p2⋅s=2⋅ps or
pq⁄q=p2⋅s⁄(2⋅s)=ps⁄s or
pq⁄q is reducible.

We can state now that for any even q, pq⁄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 pn and pn+1) satisfying
n⋅α≤p≤n⋅α+1
if, and only if n⋅α is an integer.

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

From the case 1 above n⋅α≤n⋅p1≤n⋅α+1 or pn≤n⋅p1≤pn+1 which means
pn=n⋅p1 or
pn+1=pn+1=n⋅p1

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

If p1 doesn't exists (we stated there could be maximum 1), then both pn⁄n and pn+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 pi=i⋅p1, 1≤i≤n-1. Yes, this is true, if we admit there exists p1 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.