Missouri's Reducible Fractions

Find 10 10 positive fractions each written in lowest terms, each of which is strictly less than 1 1 and any two are distinct, such that:

  • The product of all 10 10 fractions equals 1 10 \frac{1}{10} ;
  • The product of 9 9 of these 10 10 equals 1 9 \frac{1}{9} ;
  • The product of 8 8 of these 10 10 equals 1 8 \frac{1}{8} ; \vdots \qquad \vdots \qquad \vdots \qquad \vdots
  • The product of 3 3 of these 10 10 equals 1 3 \frac{1}{3} ;
  • The product of 2 2 of these 10 10 equals 1 2 \frac{1}{2} ;
  • The denominators of all these 10 10 fractions do not exceed 10 10 .

It can be shown that if S S denote the sum of unordered solution of these 10 10 fractions, then the sum of all distinct S S can be expressed as A B \dfrac{A}{B} for coprime positive integers A A and B B . Input A + B A + B as your answer.


This is originally Eastern Illinois University Math Challenge problem, which is directed from Missouri State challenge problems.


The answer is 21397.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Pi Han Goh
Jun 1, 2021

Claim: Among the 10 10 proper fractions chosen, 1 5 \frac1{5} cannot be one of them.

Proof: Suppose not. That is suppose 1 5 \frac1{5} is one of the 10 10 proper fractions, then from the 5 st 5^\text{st} bullet point, the product of half of 10 10 proper fractions is equal to 1 5 , \frac15 , and thus the product of the other half of the 10 10 proper fractions must be equal to 1 10 ÷ 1 5 = 1 2 . \frac1{10} \div \frac15 = \frac12 .

If 1 5 \frac15 is one of the 5 5 proper fractions whose product is 1 5 , \frac15, then the remaining 4 4 proper fractions have a product of 1 5 ÷ 1 5 = 1. \frac15 \div \frac15 = 1 . This is impossible because the product of positive proper fractions cannot be greater or equal to 1. 1.

If 1 5 \frac15 is one of the 5 5 proper fractions whose product is 1 2 , \frac12, then the remaining 4 4 proper fractions have a product of 1 2 ÷ 1 5 = 5 2 1. \frac12 \div \frac15 = \frac52 \geqslant 1 . This is impossible again for the same reason.

Either way, 1 5 \frac15 cannot be one of the 10 10 proper fractions.

Claim: Among the 10 10 proper fractions chosen, 1 6 , 1 7 , 1 8 , 1 9 , 1 10 \frac16, \frac17, \frac18,\frac19, \frac1{10} cannot be one of them as well.

Proof: It is the same argument as the proof above.

Next, let's figure out the number of such proper fractions whose denominators are at most 10. 10. A simple script tells us that there are 25 25 such proper fractions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from math import gcd
from fractions import Fraction

all_such_lowest_fractions = [ Fraction(a,b) for a in range(1,9 + 1) for b in range(a+1, 10 + 1) if gcd(a,b) == 1 ]

# Because we have established that neither 1/5, 1/6, ... , 1/10 can be one of them.
for d in range(5, 10 + 1):
    all_such_lowest_fractions .remove( Fraction(1,d) ) 

print(all_such_lowest_fractions)
print(len(all_such_lowest_fractions))
'''Output:
[Fraction(1, 2), Fraction(1, 3), Fraction(1, 4), Fraction(2, 3), Fraction(2, 5), Fraction(2, 7), Fraction(2, 9), Fraction(3, 4), Fraction(3, 5), Fraction(3, 7), Fraction(3, 8), Fraction(3, 10), Fraction(4, 5), Fraction(4, 7), Fraction(4, 9), Fraction(5, 6), Fraction(5, 7), Fraction(5, 8), Fraction(5, 9), Fraction(6, 7), Fraction(7, 8), Fraction(7, 9), Fraction(7, 10), Fraction(8, 9), Fraction(9, 10)]
25
'''

0 \phantom0

There is a total of ( 25 10 ) = 3 , 268 , 760 {25 \choose 10} = \numcomma{3268760} ways to select 10 10 of these fractions. To add to that, for each of these 10 10 -tuplets, we have to verify that they satisfy all the bullet points. That's quite a daunting task!

In order to reduce the number of cases to check, we will attempt to narrow down which of these 25 25 fractions must be chosen.

Claim: 6 6 of the 10 10 numbers chosen must be 4 5 , 5 6 , 6 7 , 7 8 , 8 9 , 9 10 . \dfrac45, \dfrac56, \dfrac67, \dfrac78, \dfrac89, \dfrac9{10} .

Proof: From the 1 st 1^\text{st} and 7 th 7^\text{th} bullet point, 6 6 of these proper fractions must have a product of 1 10 ÷ 1 4 = 2 5 . \dfrac1{10} \div \dfrac14 = \dfrac25 . Among the 25 25 fractions to choose from, only the largest 6 6 fractions yield such a product, 4 5 × 5 6 × 6 7 × 7 8 × 8 9 × 9 10 = 2 5 . \dfrac45 \times \dfrac56 \times \dfrac67 \times \dfrac78 \times \dfrac89 \times \dfrac9{10} = \dfrac25 . In other words, among these 25 25 fractions to choose from, 6 6 of them must be { 4 5 , 5 6 , 6 7 , 7 8 , 8 9 , 9 10 } . \left \{ \frac45, \frac56, \frac67, \frac78, \frac89, \frac9{10} \right \} .

Confirmation:

1
2
3
4
5
6
7
all_such_lowest_fractions.sort()
these_6_largest_fractions = all_such_lowest_fractions[-6:]
print(prod(these_6_largest_fractions ))
print(*these_6_largest_fractions )
# Output:
# 2/5 
# 4/5 5/6 6/7 7/8 8/9 9/10

0 \phantom0

Claim: The other 4 4 fractions must be ( 2 3 , 3 4 , 5 7 , 7 10 ) \left( \frac23, \frac34, \frac57, \frac7{10} \right) or ( 3 4 , 3 5 , 5 7 , 7 9 ) . \left( \frac34 , \frac35 , \frac57, \frac79 \right) .

Proof: From the previous claim, we have determined 6 6 fractions whose product is 2 5 , \frac25 , thus we just have to exhaustively check for all ( 25 6 10 6 ) = ( 19 4 ) = 3 , 876 {25-6 \choose 10-6} = {19 \choose 4} = \numcomma{3876} combinations of fractions that yields a product of 1 4 . \frac14 . A simple script can instantaneously produce the answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Remove these 6 fractions from the selection first:
for d in range(5, 10 + 1):
    all_such_lowest_fractions.remove(1 - Fraction(1,d))

for this_set in combinations(all_such_lowest_fractions, 4):
    if prod(this_set)  == Fraction(1,4):
        print(*this_set)
'''Output:
2/3 3/4 5/7 7/10
3/4 3/5 5/7 7/9
'''

0 \phantom0

Thus, the two solutions are:

( 2 3 , 3 4 , 4 5 , 5 6 , 5 7 , 6 7 , 7 8 , 8 9 , 7 10 , 9 10 ) \left(\dfrac23\hspace{0.5em}, \hspace{0.5em}\dfrac34\hspace{0.5em}, \hspace{0.5em}\dfrac45\hspace{0.5em}, \hspace{0.5em}\dfrac56\hspace{0.5em}, \hspace{0.5em}\dfrac57\hspace{0.5em}, \hspace{0.5em}\dfrac67\hspace{0.5em}, \hspace{0.5em}\dfrac78\hspace{0.5em}, \hspace{0.5em}\dfrac89\hspace{0.5em}, \hspace{0.5em}\dfrac7{10}\hspace{0.5em}, \hspace{0.5em}\dfrac{9}{10}\right) and ( 3 4 , 3 5 , 4 5 , 5 6 , 5 7 , 6 7 , 7 8 , 7 9 , 8 9 , 9 10 ) \left( \dfrac34 \hspace{0.5em}, \hspace{0.5em} \dfrac35\hspace{0.5em}, \hspace{0.5em} \dfrac45\hspace{0.5em}, \hspace{0.5em} \dfrac56 \hspace{0.5em}, \hspace{0.5em} \dfrac57\hspace{0.5em}, \hspace{0.5em} \dfrac67\hspace{0.5em}, \hspace{0.5em} \dfrac78\hspace{0.5em}, \hspace{0.5em} \dfrac79 \hspace{0.5em}, \hspace{0.5em} \dfrac89\hspace{0.5em}, \hspace{0.5em} \dfrac9{10}\right)

Let's verify that these 2 2 solutions satisfy all the given bullet points.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
product_of_how_many = lambda give_me_10_fractions, pick_how_many : \
                    any( prod(these_n_tuplets) == Fraction(1,pick_how_many) 
                            for these_n_tuplets in combinations(give_me_10_fractions, pick_how_many) )

are_all_the_bullet_points_true = lambda give_me_ten_fractions : \
                                all( product_of_how_many(give_me_ten_fractions, k) for k in range(2, 10 + 1) )

first_solution = [Fraction(2, 3), Fraction(3, 4), Fraction(4, 5), Fraction(5, 7), Fraction(7, 10), 
                    Fraction(5, 6), Fraction(6, 7), Fraction(7, 8), Fraction(8, 9), Fraction(9, 10)]

second_solution = [Fraction(3, 4), Fraction(3, 5), Fraction(4, 5), Fraction(5, 7), Fraction(7, 9), 
                    Fraction(5, 6), Fraction(6, 7), Fraction(7, 8), Fraction(8, 9), Fraction(9, 10)]

print( are_all_the_bullet_points_true(first_solution) )
print( are_all_the_bullet_points_true(second_solution) )
# Output:
# True
# True

0 \phantom0

The answer follows.

1
2
3
4
final_fraction = sum(first_solution) + sum(second_solution)

print(final_fraction.numerator + final_fraction.denominator)
# 21397

0 \phantom0


What's incredible is that the results produced from the scripts are all instantaneous!

For completeness, for the first set of solution:

2 3 , 3 4 , 4 5 , 5 6 , 5 7 , 6 7 , 7 8 , 8 9 , 7 10 , 9 10 \dfrac23, \hspace{1em}\dfrac34, \hspace{1em}\dfrac45, \hspace{1em}\dfrac56, \hspace{1em}\dfrac57, \hspace{1em}\dfrac67, \hspace{1em}\dfrac78, \hspace{1em}\dfrac89, \hspace{1em}\dfrac7{10}, \hspace{1em}\dfrac{9}{10}

1 / 2 = 2 / 3 × 3 / 4 = 5 / 7 × 7 / 10 1 / 3 = 2 / 3 × 5 / 7 × 7 / 10 1 / 4 = 2 / 3 × 3 / 4 × 5 / 7 × 7 / 10 1 / 5 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 7 × 7 / 10 1 / 6 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 6 × 5 / 7 × 7 / 10 1 / 7 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 10 1 / 8 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 10 × 7 / 8 1 / 9 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 10 × 7 / 8 × 8 / 9 1 / 10 = 2 / 3 × 3 / 4 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 10 × 7 / 8 × 8 / 9 × 9 / 10 \begin{array} { l c l } 1/2 &=& 2/3\times3/4 = 5/7 \times 7/10 \\ 1/3 &=& 2/3\times5/7\times7/10 \\ 1/4 &=& 2/3\times3/4\times5/7\times7/10 \\ 1/5 &=& 2/3\times3/4\times4/5\times5/7\times7/10 \\ 1/6 &=& 2/3\times3/4\times4/5\times5/6\times5/7\times7/10 \\ 1/7 &=& 2/3\times3/4\times4/5\times5/6\times5/7\times6/7\times7/10 \\ 1/8 &=& 2/3\times3/4\times4/5\times5/6\times5/7\times6/7\times7/10\times7/8 \\ 1/9 &=& 2/3\times3/4\times4/5\times5/6\times5/7\times6/7\times7/10\times7/8\times8/9 \\ 1/10 &=& 2/3\times3/4\times4/5\times5/6\times5/7\times6/7\times7/10\times7/8\times8/9\times9/10 \end{array}


And for the second set of solution:

3 4 , 3 5 , 4 5 , 5 6 , 5 7 , 6 7 , 7 8 , 7 9 , 8 9 , 9 10 \dfrac34 , \hspace{1em} \dfrac35, \hspace{1em} \dfrac45, \hspace{1em} \dfrac56 , \hspace{1em} \dfrac57, \hspace{1em} \dfrac67, \hspace{1em} \dfrac78, \hspace{1em} \dfrac79 , \hspace{1em} \dfrac89, \hspace{1em} \dfrac9{10}

1 / 2 = 3 / 5 × 5 / 6 1 / 3 = 3 / 5 × 5 / 7 × 7 / 9 1 / 4 = 3 / 4 × 3 / 5 × 5 / 7 × 7 / 9 1 / 5 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 7 × 7 / 9 1 / 6 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 6 × 5 / 7 × 7 / 9 1 / 7 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 9 1 / 8 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 9 × 7 / 8 1 / 9 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 9 × 7 / 8 × 8 / 9 1 / 10 = 3 / 4 × 3 / 5 × 4 / 5 × 5 / 6 × 5 / 7 × 6 / 7 × 7 / 9 × 7 / 8 × 8 / 9 × 9 / 10 \begin{array} { l c l } 1/2 &=& 3/5\times5/6 \\ 1/3 &=& 3/5\times5/7\times7/9 \\ 1/4 &=& 3/4\times3/5\times5/7\times7/9 \\ 1/5 &=& 3/4\times3/5\times4/5\times5/7\times7/9 \\ 1/6 &=& 3/4\times3/5\times4/5\times5/6\times5/7\times7/9 \\ 1/7 &=& 3/4\times3/5\times4/5\times5/6\times5/7\times6/7\times7/9 \\ 1/8 &=& 3/4\times3/5\times4/5\times5/6\times5/7\times6/7\times7/9\times7/8 \\ 1/9 &=& 3/4\times3/5\times4/5\times5/6\times5/7\times6/7\times7/9\times7/8\times8/9 \\ 1/10 &=& 3/4\times3/5\times4/5\times5/6\times5/7\times6/7\times7/9\times7/8\times8/9\times9/10 \end{array}

Pi Han Goh - 1 week, 3 days ago

That'll explain why I couldn't prove uniqueness! It's extraordinary that there are precisely two solutions.

Chris Lewis - 1 week, 3 days ago
Chris Lewis
Jun 1, 2021

Say the fractions are, in some order, x 1 , x 2 , , x 10 x_1,x_2,\ldots,x_{10} . Obviously there are lots of ways we could pick, say, the five fractions whose product has to be one fifth ( 252 252 ways, to be exact), so in most cases we can't immediately assign the fractions to their given products in most cases; but let's be more optimistic. We can say that i = 1 10 x i = 1 10 \prod_{i=1}^{10} x_i=\frac{1}{10}

and, since we can choose the labelling of the x i x_i , we can have i = 1 9 x i = 1 9 \prod_{i=1}^{9} x_i=\frac{1}{9}

Comparing these, we get x 10 = 9 10 x_{10}=\frac{9}{10} . In fact, if we assume that the fractions not included in the next product are x 9 , x 10 x_9,x_{10} , we'd get i = 1 8 x i = 1 8 \prod_{i=1}^{8} x_i=\frac{1}{8}

and x 9 = 8 9 x_9=\frac89 . It's clear that we can keep going like this, following the pattern x i = i 1 i x_i=\frac{i-1}{i} for i > 1 i>1 .

Of course, now we see the problem: if x 2 = 1 2 x_2=\frac12 , we would need x 1 = 1 x_1=1 , which - although it would satisfy all the required products - is not allowed in the conditions.

Remaining optimistic (if a bit less so), let's instead say that x i = i 1 i x_i=\frac{i-1}{i} for i > 2 i>2 , and seek a pair of fractions x 1 , x 2 x_1,x_2 not already in this list such that x 1 x 2 = 1 2 x_1 x_2=\frac12 .

Say that x 1 = p q x_1=\frac{p}{q} and x 2 = r s x_2=\frac{r}{s} , where p , q , r , s p,q,r,s are positive integers and the fractions are in lowest terms. Then we need 2 p r = q s , 1 < q s 10 2pr=qs,\;\;\;1<q\le s \le 10 (where again we're free to choose q s q\le s .) We also need p < q 1 p<q-1 and r < s 1 r<s-1 , so as not to clash with one of the x i x_i we've already chosen.

It's a bit of casework but not too hard to show that the unique pair of fractions satisfying these conditions are x 1 = 5 7 x_1=\frac57 and x 2 = 7 10 x_2=\frac{7}{10} . The complete list of fractions is then 5 7 , 7 10 , 2 3 , 3 4 , 4 5 , 5 6 , 6 7 , 7 8 , 8 9 , 9 10 \frac57,\frac{7}{10},\frac23,\frac34,\frac45,\frac56,\frac67,\frac78,\frac89,\frac{9}{10} and it's easy to verify that the product of the first n n fractions in this list is 1 n \frac{1}{n} .

The sum of these fractions is 20123 2520 \boxed{\frac{20123}{2520}} .

Note that this approach finds a set of fractions that works, but doesn't prove uniqueness (we made an assumption in calculating x 9 x_9 but it doesn't rule out other possibilities).

We have a product of 2 distinct proper fractions that is equal to 1 10 ÷ 1 8 = 4 5 . \dfrac1{10} \div \dfrac18 = \dfrac45.

Let these two fractions be a b \dfrac ab and c d , \dfrac cd, where 1 a < b 10 , 1 c < d 10 , gcd ( a , b ) = gcd ( c , d ) = 1 , a b c d 1\leqslant a < b \leqslant 10, \hspace{5em} 1\leqslant c<d\leqslant 10, \hspace{5em} \gcd(a,b)= \gcd(c,d) = 1, \hspace{5em} \dfrac ab \ne \dfrac cd

If we exhaustively search for all such integers, we can conclude that two of these ten fractions are 8 9 \dfrac89 and 9 10 . \dfrac9{10} .

Pi Han Goh - 1 week, 4 days ago

Say that x 1 = p q x_1=\frac{p}{q} and x 2 = r s x_2=\frac{r}{s} , where p , q , r , s p,q,r,s are positive integers and the fractions are in lowest terms. Then we need 2 p r = q s , 1 < q s 10 2pr=qs,\;\;\;1<q\le s \le 10 (where again we're free to choose q s q\le s .) We also need p < q 1 p<q-1 and r < s 1 r<s-1 , so as not to clash with one of the x i x_i we've already chosen.

It's a bit of casework but not too hard to show that the unique pair of fractions satisfying these conditions are x 1 = 5 7 x_1=\frac57 and x 2 = 7 10 x_2=\frac{7}{10} .

This isn't necessarily true. Note that in my second set of solution, none of the fractions chosen is equal to 7 10 . \dfrac7{10}. Plus, what's stopping us from choosing another pair of fractions such that their product is 1 2 \dfrac12 as well?

Also, ( 5 7 , 7 10 ) \left(\dfrac57, \dfrac7{10} \right) is not the only pair of proper fractions that satisfy the 9 th 9^\text{th} bullet point.

The other pairs that doesn't clash with the earlier x i x_i 's chosen are:

( 2 3 , 3 4 ) , ( 3 5 , 5 6 ) , ( 4 5 , 5 8 ) , ( 4 7 , 7 8 ) \left(\dfrac23, \dfrac34\right), \hspace{1em}\left(\dfrac35, \dfrac56\right),\hspace{1em} \left(\dfrac45, \dfrac58\right),\hspace{1em} \left(\dfrac47, \dfrac78\right)

Pi Han Goh - 1 week, 3 days ago

Log in to reply

Er...all of those pairs have a clashing fraction! Remember the "earlier chosen x i x_i s" in my solution are the fractions of the form x i = i 1 i x_i=\frac{i-1}{i} for i = 3 , 4 , , 10 i=3,4,\ldots,10 , ie 2 3 , 3 4 , 4 5 , 5 6 , 6 7 , 7 8 , 8 9 , 9 10 \frac23,\frac34,\frac45,\frac56,\frac67,\frac78,\frac89,\frac{9}{10}

In the four pairs you list, you have clashes with 2 3 \frac23 and 3 4 \frac34 in the first one, 5 6 \frac56 in the second, 4 5 \frac45 in the third and 7 8 \frac78 in the fourth.

The point - not that there was much of a point - to my solution was that the naïve approach of trying to construct the set of x i x_i in the simplest way works. No reordering of the x i x_i is needed; they satisfy i = 1 n x i = 1 n \prod_{i=1}^n x_i = \frac{1}{n} for n > 1 n>1 .

I'm pretty sure the set I found is the unique with this property. However, as you showed, it's not the unique set answering the original question. (Note though that your second set doesn't have the property above.)

This was the only way I could think of to find a solution by hand - I'm still not sure whether that was a requirement in the inspiration for this question.

Chris Lewis - 1 week, 3 days ago

Log in to reply

Ah my apologies. I made the same wishful thinking about generating these fractions via x i = 1 1 i x_i = 1- \frac1i but I couldn't justify why the first set of solution works. And I tried to prove its uniqueness. But as you can see, it failed spectacularly.

Pi Han Goh - 1 week, 3 days ago

I've updated my solution. You might be interested to see that with barely any casework, we can deduce that 5 5 of the 10 10 fractions must be the 5 5 largest permissible fractions possible:

{ 5 6 , 6 7 , 7 8 , 8 9 , 9 10 } \left \{ \dfrac56, \dfrac67, \dfrac78, \dfrac89, \dfrac9{10} \right \}

Pi Han Goh - 1 week, 3 days ago

Log in to reply

Wow, that's a great insight in your update. Now you've got this perhaps it's possible to solve the rest by hand too? It really limits the options. Consider how to make 1 2 \frac12 as the product of two fractions. With all denominators less than 11 11 , the only way we can use fractions from this list is as one of 5 6 3 5 , 7 8 4 7 , 9 10 5 9 \frac56 \cdot \frac 35,\;\;\frac78 \cdot \frac 47,\;\;\frac{9}{10} \cdot \frac59

Without using any of these fractions, we can have 2 3 3 4 , 4 5 5 8 , 5 7 7 10 \frac23 \cdot \frac 34,\;\;\frac45 \cdot \frac 58,\;\;\frac57 \cdot \frac{7}{10}

In the first case we get 6 6 of the full set of fractions, and know the product of the other 4 4 ; in the second case we know 7 7 and the product of the other 3 3 . Still quite a bit of case analysis to go, though.

Chris Lewis - 1 week, 3 days ago

Log in to reply

Sorry, make that 6 of 10, not 5 of 10:

{ 4 5 , 5 6 , 6 7 , 7 8 , 8 9 , 9 10 } \left \{ \dfrac45, \dfrac56, \dfrac67, \dfrac78, \dfrac89, \dfrac9{10} \right \}

Pi Han Goh - 1 week, 3 days ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...