Fracmax
Find the maximum value of 1/p + 1/q + 1/r where this sum is less than 1 and p, q, and r are positive integers.
Age
14 to 16
Challenge level
Find the maximum of
$${1\over p} + {1\over q} + {1\over r}$$
where $p$, $q$ and $r$ are positive integers and
$${1\over p} + {1\over q} + {1\over r} < 1.$$
Prove that it is indeed a maximum.
Substitute some numerical values in a systematic way and make a conjecture about the maximum. Then prove your conjecture.
There were a number of good solutions to this problem and I have picked several to illustrate the different approaches adopted.
First Fred and Matt from Albion Heights sent in a solution, which I rather liked. They have not explained why they did not try 1/3 as the first fraction or give full reasoning for why they knew they had a largest value, but the argument as far as it goes is a good one. I have added some examples below to illustrate what they said in a little more detail. I have included a solution based on the one from Tom or STRS, which was similar to that of Curt from Reigate School . Andrei, of Tudor Vianu College, also looked for solutions using a spreadsheet and sent in a program in C++ to search for soultions. I have included this below.
Well done to all of you.
First Fred and Matt's approach to get us started::
To crack the puzzle we tried using algebra but it did not work
so we took this problem from a different approach.
Our answer to this puzzle is p=2 q=3 and r=7 and this would
end up like this 1/2+1/3+1/7=41/42 .
We also tried a number of other combination but none of them
was as close as this one and this is how we were thinking:
If one of the fractions is 1/2 then this puzzle would be
slightly easier. Then we had to try the other two numbers. Of couse
the total of the other two should be less than 1 otherwise this
puzzle would equal or be more than one so the second number has to
be 1/3 1/4 1/5 .... and so on.
If you take1/3 for one of the fractions, the last number has
to be 1/7 for the closest result (the bigger the denominator is the
smaller the number is).
If you take 1/4 then the last fraction would be 1/3 for the
closest result.
Then we figure out when we use 1/2 then all we have to do is
find two other numbers that add up to less than 1/2 and we know
that 1/3 and 1/6 add to 1/2 so instead of 6 we used 7 and this made
the answer smaller because the denonminator is bigger.
To make a fraction as large as possible you need to make the denominator as small as possible. The smallest a denominator can be is $2$. All the denominators cannot be $2$ because:
$$ \frac{1}{2} + \frac{1}{2} + \frac{1}{2}= \frac{3}{2} \mbox{ which is }> 1 $$
The next we can try then is
$$ \frac{1}{2} + \frac{1}{3} + \frac{1}{2}= \frac{4}{3} \mbox{ which is }> 1 $$
Then try the next largest value, which is:
$$ \frac{1}{2} + \frac{1}{3} + \frac{1}{3}= \frac{7}{6} \mbox{ which is }> 1 $$
This is getting closer to $1$ but is still greater than $1$
Try denominators of $2$, $3$ and $4$ giving:
$$ \frac{1}{2} + \frac{1}{3} + \frac{1}{4}= \frac{13}{12} \mbox{ which is }> 1 $$
Continuing in this way, the first set of fractions that give a total less than $1$ and with the smallest possible denominators (and largest sum) is:
$$ \frac{1}{2} + \frac{1}{3} + \frac{1}{7}= \frac{41}{42} \mbox{ which is }< 1$$
I will use the notation $(p,q,r)$ when referring to set of
values for the variables.
First I will eliminate the '3rd dimension' to this problem by
proving that p = 2. To simplify the explanation I will always have
p as the lowest variable, this is OK as p q and r are
interchangeable without affecting the sum.
If $p = 3, q > = 3$ and $r > =3$ as $p$ is the lowest
variable. The greatest sum in this case is: $ (3,3,4)=
11/12$ as this is the minimum value each variable can take,
therefore maximising the reciprocals. $(3,3,3)$ gives $1$ exactly
which is not permissible as the sum must be $< 1$.
For p > = 4, the greatest sum will be given by $p, q$ and
$r$ all being equal ie $(p,p,p)$, as this minimises them (they
cannot be higher than $p$ as that is the lowest). The sum will
be:
$$3 \times( 1 / p ) = 3 / p$$
As $p > = 4$, this cannot exceed $3/4$. Now consider the
case $(2,3,7)$. The sum here is $41/42$, which is greater than the
maximum established for $p = 3$ and $p \geq 4$. As $p$ is a
positive integer, and $p = 0, p = 1$ both invalidate the condition
that the sum must be lower than $1$, it is proven that $p =
2$.
The solution is $(2,3,7)$, or if there is a one greater still
it too must occur where $p = 2$.
Now I will prove that $(2,3,7)$ in fact gives the
maximum.
It is proven that $p = 2$, therefore:
\begin{eqnarray} 1/2 + 1/q + 1/r &< & 1\\ 1/q + 1/r
&< & 1/2\\ q + r &< & qr/2\\ 2q + 2r - qr
&< & 0\\ qr - 2q - 2r&> & 0\\ q(r - 2) - 2r
&> & 0\\ q(r - 2) &> & 2r\\ q &> &
(2r)/(r-2) \end{eqnarray}
If there is a solution better than that of (2,3,7), the
following inequality must hold true:
\begin{eqnarray} 1/2 + 1/q + 1/r &> &41/42\\ 1/q +
1/r&> & 10/21\\ 21q + 21r &> & 10qr\\ 21q +
21r - 10qr &> & 0\\ 10qr - 21q - 21r &< & 0\\
q(10r - 21) - 21r &< & 0\\ q(10r - 21) &< &
21r\\ q &< & (21r)/(10r-21)\\ \end{eqnarray}
So it is established that
$$(2r)/(r-2) < q < (21r)/(10r-21)$$
Now I will show there are no solutions that will match this
inequality. Here are some individual cases:
r = 3: 6 < q < 7
r = 4: 4 < q < 4.421...
r = 5: 3.333... < q < 3.621...
r = 6: 3 < q < 3.231...
r = 7: 2.8 < q < 3
r = 8: 2.666... < q < 2.739
None of these inequalities has an integer solution. As $r$
tends to infinity $(2r)/(r-2)$ tends to $2$ and $(21r)/(10r-21)$
tends to $2.1$. Therefore the upper bound will not exceed $3$ for
$r > 8$, so the inequality will continue to fail as $q \geq
3$.
Therefore the inequality $(2r)/(r-2) < q <
(21r)/(10r-21)$ has no integer solutions for $q \geq 3, r \geq
3$.
Therefore as shown earlier there is no case for $p = 2$ that
yields a greater sum than the case $(2,3,7)$.
So
$p=2$
$q=3$
$r=7$
Andrei's program (I haven't tested it!):
//fracmax
\#include< iostream.h>
long double p,q,r,p1,q1,r1,max1;
void main() \{
max1=0;
for(p=1;p< =20;p++) \{
\hspace{10pt} for(q=1;q< =20;q++) \{
\hspace{20pt} for(r=1;r< =20;r++) \{
\hspace{30pt} if((1/p)+(1/q)+(1/r)< 1 \&\&
1/p+1/q+1/r> max1) \{
\hspace{30pt} max1=(1/p)+(1/q)+(1/r);p1=p;q1=q;r1=r;
\hspace{30pt} \}
\hspace{20pt} \}
\hspace{10pt} \}
\}
cout< < "p= "< < p1< < "; q= "< <
q1< < "; r= "< < r1< < "; maximum= "< <
max1;
\}
In order to maximise the reciprocals we want to make $p$, $q$ and $r$ as small as possible. What happens when $p\geq 3$? Investigate values for $p=2$.