Before we start the proof, note that if x=(q-p)/p, where p and q are coprime integers,
p < q < 2p, then 1/(x+1) = p/q. Also, if x=p/(q-p), where p and q are coprime integers,
2p < q, then x/(x+1) = p/q. This suggests a method of determining
whether an element is in S by applying rule 2 in reverse, to see if we end up
with 1/2.
Start with a fraction, p/q, expressed in lowest terms. Replace the
fraction with either (q-p)/p or p/(q-p), whichever is smaller. If we
eventually reach 1/2, then p/q was an element of S.
Here's an example: Starting with 19/64, we repeatedly subtract the numerator
from the denominator, and then if the result is greater than one, flip the
fraction:
19/64 -> 19/45 -> 19/26 -> 7/19 -> 7/12 -> 5/7 -> 2/5 -> 2/3 -> 1/2.
Clearly, this chain can be followed in reverse using rule 2 to show that
19/64 is an element of S. With these facts in mind, we will start a proof by contradiction.
Proof:
Consider the set of all rational numbers in the interval (0,1) that are not elements of S.
Express each of these rational numbers in lowest terms, find one with the smallest
denominator, and call it p/q.
p/q is not equal to 1/2 because it's not in S. So either q < 2p (case
1), or q > 2p (case 2).
Case 1: If q < 2p then x=(q-p)/p could not be an element of S, because if it were, then 1/(x+1) = p/q would also be in S.
But then (q-p)/p is a rational number with a smaller denominator than q, contradicting the assumption that q is the smallest denominator of any lowest-terms rational number not in S.
Case 2: If q > 2p then x=p/(q-p) could not be an element of S, because if it were, then x/(x+1) = p/q would also be in S.
Again, p/(q-p) is a rational number with a smaller denominator than q, another contradiction.
The proof by contradiction is complete, so there is no rational number, p/q, which is not an element of S.
More about this puzzle
Do you see Euclid's
Algorithm buried in this question (or its answer)? | 