Copyright © University of Cambridge. All rights reserved.
'The Clue Is in the Question' printed from https://nrich.maths.org/
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