Which number is smaller, 1/6 or 1/7? The answer should be intuitively clear (without needing to find a common denominator!) and therefore it is instructive as well. Now let’s make it more exciting by taking it as far as we can.
First, we make it into a general fact:
Fact 1: Whenever n is a positive real number, 1/(n+1) < 1/n.
Furthermore, since 1/7 < 1/6, we can subtract each fraction from 1 to see that 6/7 is closer to 1 than 5/6 is; we easily deduce that 5/6 < 6/7 and get a new fact! Another tool for the toolbox of the intuition:
Fact 2: Whenever n is a positive real number, (n-1)/n < n/(n+1).
Now for a more exciting question:
Find integers a and b such that
5/6 < a/b < 6/7.
The most common (reflex) reaction is to find the common denominator (42), and to find a fraction between 35/42 and 36/42 (for example, 71/84).
But let’s make this problem much more interesting by requiring that you find the fraction a/b with the smallest possible integer denominator. A denominator much smaller than 84 would surely mean a numerator much smaller than 71.
Thus, inspired by our two Facts, (and eager to use them wherever we can) let’s focus on the numerator.
Warm-up question 1: Is it possible that a=b-1? (can our in-between fraction a/b have a numerator that’s 1 less than its denominator? Recall 5/6 < a/b < 6/7.)
Fact 2 is very well-suited for assisting with the answer this question! Indeed, for a/b to satisfy both inequalities, b would need to be between 6 and 7. Our first warm-up question was even a bit silly. Undeterred we ask:
Warm-up question 2: Is it possible that a=b-2? (Recall 5/6 < a/b < 6/7.)
As an example, we consider b=8. One of the inequalities holds, namely 6/8 < 6/7, which we see by using Fact 1 with n=7. However, the left inequality does not hold: 5/6 is not smaller than 6/8. Why? Because 6/8 = 3/4 and 3/4 < 5/6 (by Fact 2).
Let’s try another example, b=9. By way of analogy, we expect 7/9 < 6/7 but we don’t believe the other inequality (i.e. we expect that 5/6 > 7/9). Last time, we reduced a fraction, noticing that 6/8 = 3/4, so that we could use Fact 2. It doesn’t seem that we have such luck here; but we do: 7/9 = 3.5/4.5, and Fact 2 works for all real numbers; we see exactly where 3.5/4.5 fits!
If we want to use Fact 2 on the fraction a/b we would, in the same way, “reduce” it by using half of the original numerator a and half of the original denominator b. The advantage is that Fact 2 now explains everything. In particular, the new denominator b/2 must be strictly between 6 and 7. Since b is an integer, b/2=6.5. Thus, b=13. Our fraction is thus found:
5/6 < 5.5/6.5 < 6/7… Whoops, I mean:
5/6 < 11/13 < 6/7.
But is 13 the smallest possible (positive integer) denominator? The answer lies with:
Warm-up question 3: Is it possible for a < b-2? (Recall 5/6 < a/b < 6/7.)
At this point, the question is hardly a “warm-up” but I’m calling it that, since it’s similar to the other warm-up questions.
Another way of asking the same thing: Is 2 the smallest option for b-a? We know b-a is at least 2 and that 13 is the smallest denominator with b-a=2. Could b-a=3? At this point the same style of argument works. Thus, we “reduce” the fraction by replacing the numerator a with a new numerator (1/3)a and replace the denominator b with new denominator b/3. Even if the denominator is no longer an integer, the numerator is 1 less than it, so we can still use Fact 2. With b/3 > 6, we see that b > 18. If b-a > 3 then b would be even bigger. Thus, if we are looking for the smallest denominator, then b-a=2.
Now for a similar question, from the 54th William Lowell Putnam Mathematical Competition for Undergraduate students:
Question from the 54th Putnam:
Find the smallest positive integer b such that for every integer m with 0<m<1993, there exists an integer a for which m/1993 < a/b < (m+1)/1994.
It’s not quite the same as the question we’ve been considering, but if we alter the question by fixing m=1992 then it’s fairly close to it!
Indeed, we just finished a miniature version of the m=1992 special case, by discovering that 5/6 < a/b < 6/7 has a solution with b=6+7. Thus, we might guess that b=1993+1994=3987 is the answer for the Putnam Question. It’s suggested by the special case where m=1992. But will this choice of b work for every m?
Let’s return to our smaller question and make the comparison with the Putnam question more exact.
Small version of Putnam Question:
Find the smallest positive integer b such that for every integer m with 0<m<6, there exists an integer a for which m/6 < a/b < (m+1)/7.
We know from our work that the answer is at least b=13 (to accommodate m=5) and we expect the answer is b=13. To be sure, we need to know that there are integer answers to the following questions:
Question 1: 1/6 < ?/13 < 2/7 (corresponds with m=1)
Question 2: 2/6 < ?/13 < 3/7 (m=2)
Question 3: 3/6 < ?/13 < 4/7 (m=3)
Question 4: 4/6 < ?/13 < 5/7 (m=4)
We’ll focus on Question 1 and the rest will fall into place. We want to know if:
1/6 < a/13 < 2/7 has an integer solution for a. We need a slightly improved version of Fact 1:
Fact 1 (improved): If m > n > 0 then 1/m < 1/n. (The previous version essentially had m=n+1. We will need m=n+0.5).
We use this by observing that 2/13 = 1/6.5; hence we see that 2/13 is too small (i.e. a>2). On the other hand, since 4/13 = 2/6.5, we know that 4/13 is too big and hence a<4. (We used the improved version of Fact 1 again). Hence a=3 is the only possibility. We check if it works:
1/6 < 3/13 < 2/7. This may look more appealing to us (based on our work so far) if we write:
1/6 < 1.5/6.5 < 2/7. Perhaps one more equivalent form:
2/12 < 3/13 < 4/14.
This looks very compelling and suggests another fact:
Fact 3: Assume y > x > 0. Then x/y < (x+1)/(y+1).
This can be very intuitive. If you follow any sports team who wins x of their first y games, and they win their next game, their proportion of games won has surely gone up! The proof is almost as easy. Read it backwards:
Proof of Fact 3:
x/y < (x+1)/(1+y)
End of proof.
Question 2 is now easy, since Fact 3 yields
4/12 < 5/13 < 6/14.
Question 3 and 4 are almost the same.
Thus, while we are still far away from a formal proof; our made-up “small version” of the Putnam Question is not that hard; the actual Putnam Question works on the same principles (try it!). It’s fun if we’ve been thinking about the ideas. A formal solution and full proof can be quite short and elegant. Three such solutions are given in “The William Lowell Putnam Mathematical Competition 1985-2000” by Kedlaya, Poonen and Vakil. Our above discussion is an attempt to make the problem seem like a natural extension of very elementary ideas.
- If a, b, c and d are all positive real numbers, and if a/b < c/d then a/b < (a+c)/(b+d) < c/d. This is a popular, more general version of Fact 3 and just as easy to prove. We will explore this further in an upcoming follow-up post, “Fun with Fractions—from elementary arithmetic to the Putnam Competition—the second 1/2.”
- Among many (social) circles, Putnam Questions have a reputation of being too difficult to be useful. My attitude is that on every Putnam Competition, there is at least one question per session where a less experienced problem-solver can play with the ideas and learn a great deal, even without solving it. This may be such a problem.