|
|
|
Let S be a set of rational numbers with the following properties:
1) 1/2 is an element of S
2) If x is an element of S, then both 1/(x+1) is an element of S and x/(x+1) is
an element of S
Prove that S contains all rational numbers in the interval 0<x<1.
Source: unknown
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.
Do you see Euclid's Algorithm buried in this question (or its answer)?
One person observed that since all rational numbers have a simple (i.e. finite length) continued fractions representation and all of the numbers used to evaluate the continued fraction are in S (for rationals between 0 and 1) then all rational numbers between 0 and 1 are in S.
This person started by proving by induction that if 1/p is in S, then 1/(p+1) is also in S ((1/p)/((1/p)+1) = 1/(p+1)), so all 1/n are in S.
Then, he proved by induction that if x is an element of S, then 1/(n+x) is also an element of S for any positive integer n. His proof starts by noting that 1/(x+1) is an element of S, and so (1/(n+x))/((1/(n+x))+1) = 1/((n+1)+x) is also in S.
Finally, he observed that each step of every finite-length continued fraction consists of an element of S, thus every rational is an element of S.
Cut the knot: Euclid's Algorithm.
The Broken Calculator Puzzle. In this puzzle, a calculator initially showing 0 can be made to show any rational number by pressing sin, cos, tan and their inverses in some order a finite number of times. The method and the proof are similar to this puzzle.
The webmaster and author of this Math Help site is Graeme McRae.