Challenge Level

James Bell from the MacMillan academy sent in his impressive solution to this difficult problem. Our congratulations go to James!

Steve says, the argument runs as follows:

1. N and D map proper fractions to proper fractions.

2. The inverses of N and D are unique fractions F.

3. The numerators and denominators never decrease following a transformation.

5. There are no fixed points of $N$ and $D$.

Putting these points together show that any proper fraction is in the set $F$: pick a proper fraction and you can always work backwards in a chain which leads to the proper fraction $\frac{1}{2}$.

James writes:

Applying rule 2 to $\frac{x}{y-x}$ gives $\frac{x}{y}$

Applying rule 3 to $\frac{y-x}{x}$ gives $\frac{x}{y}$

So, $\frac{x}{y}$ is a member of F if either $\frac{x}{y-x}$ or $\frac{y-x}{x}$ are members of F.

Any rational number between 0 and 1 can be written x/y where x and y are integers that share no common factors except 1. Given any such x and y either:

1) (y-x)> x in which case x/(y-x) (as x and y share no common factors except 1 neither can x and y-x) is a rational number between 0 and 1 with numerator+denominator less than x/y (y rather than x+y), whose presence in F would imply x/y's presence by rule 2

2) (y-x)< x in which case (y-x)/x (as x and y share no common factors except 1 neither can x and y-x) is a rational number between 0 and 1 with numerator+denominator less than x/y (y rather than x+y), whose presence in F would imply x/y's presence by rule 3

or 3) (y-x)=x and y=2x so x/y=x/2x=1/2 which we know to be a member of F using these rules

Given x/y, such that x+y> 3, we can generate either x/(y-x) or (y-x)/x (less than 1 greater than 0) whose presence in F implies x/y's presence and has smaller numerator over denominator. If we repeat this algorithm numerator+denominator must eventually fall to 0,1,2 or 3 (can't be negative as numerator and (denominator-numerator) must always be positive as they were to begin with and denominator is always greater than numerator, fraction is < 1)

case 0: only possibility 0/0 which can't be reached as it is not greater than 0

case 1:either 1/0 which can't be reached because it has greater numerator than denominator or 0/1 which can't be reached because it is not greater than 0.

case 2: 2/0 (numerator> denominator), 0/2 is not > 0, 1/1 is not < 1 case 3: 3/0 (numerator> denominator), 0/3 is not > 0, 2/1 is not < 1

which leaves from all cases only 1/2 (which we know is a member of F) can be reached and therefore must be the ultimate destination of all x/y defined above as we apply the algorithm above.

And so as 1/2 is in F so are all x/y (in lowest terms and between 0 and 1)

and so all rational numbers between 0 and 1 are in F QED