The Clue Is in the Question

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