The Clue Is in the Question
Age 16 to 18
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