Maths Olympiad Prep

Library / /143 of 144

Algebra Difficulty 3.0 AMC 10/12 Find the answer

A set consists of five different odd positive integers, each greater than 2. When these five integers are multiplied together, their product is a five-digit integer of the form AB0ABAB0AB, where AA and BB are digits with A0A \neq 0 and ABA \neq B. (The hundreds digit of the product is zero.) For example, the integers in the set {3,5,7,13,33}\{3,5,7,13,33\} have a product of 45045. In total, how many different sets of five different odd positive integers have these properties?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solution 1: Let N=AB0ABN=AB0AB and let tt be the two-digit integer ABAB. We note that N=1001tN=1001t, and that 1001=1191=117131001=11 \cdot 91=11 \cdot 7 \cdot 13. Therefore, N=t71113N=t \cdot 7 \cdot 11 \cdot 13. We want to write NN as the product of 5 distinct odd integers, each greater than 2, and to count the number of sets SS of such odd integers whose product is NN. There are several situations to consider. First, we look at possible sets SS that include the integers 7, 11 and 13 (which we know are divisors). Second, we look at possible sets SS that include two of these integers and an odd multiple of the third. Third, we rule out possible sets SS that include one of these integers and odd multiples of the second and third. Fourth, we rule out possible sets SS that include the product of two or three of these integers and additional integers. Case 1: S={7,11,13,m,n}S=\{7,11,13, m, n\} where m<nm<n and m,n7,11,13m, n \neq 7,11,13 Here, N=71113mn=mn1001N=7 \cdot 11 \cdot 13 \cdot m \cdot n=mn \cdot 1001 and so t=mnt=mn. This tells us that mnmn is less than 100. If m=3m=3, then the possible values for nn are 5,9,15,17,19,21,23,25,27,29,315,9,15,17,19,21,23,25,27,29,31. These give the following corresponding values of mnmn: 15,27,45,51,57,63,69,75,81,87,9315,27,45,51,57,63,69,75,81,87,93. Note that n33n \neq 33, since m=3m=3 and n=33n=33 gives mn=99mn=99 which has two equal digits and so is not possible. If m=5m=5, then the possible values for nn are 9,15,17,199,15,17,19. If m9m \geq 9, then n15n \geq 15 since the integers in nn are odd and distinct, and so mn135mn \geq 135, which is not possible. Therefore, in this case, there are 15 possible sets. Case 2: S={7q,11,13,m,n}S=\{7q, 11,13, m, n\} where m<nm<n and q>1q>1 is odd and m,n7q,11,13m, n \neq 7q, 11,13 Here, we have N=7q1113mnN=7q \cdot 11 \cdot 13 \cdot m \cdot n and so N=1001mnqN=1001 \cdot mnq which gives t=mnqt=mnq. Note that mnq99mnq \leq 99. Suppose that q=3q=3. This means that mn33mn \leq 33. If m=3m=3, then the possible values of nn are 5 and 9 since mm and nn are odd, greater than 2, and distinct. (n=7n=7 is not possible, since this would give the set {21,11,13,3,7}\{21,11,13,3,7\} which is already counted in Case 1 above.) If m5m \geq 5, then n7n \geq 7 which gives mn35mn \geq 35, which is not possible. Suppose that q=5q=5. This means that mn995=1945mn \leq \frac{99}{5}=19 \frac{4}{5}. If m=3m=3, then n=5n=5. There are no further possibilities when q=5q=5. Since mn35=15mn \geq 3 \cdot 5=15 and mnq99mnq \leq 99, then we cannot have q7q \geq 7. Therefore, in this case, there are 3 possible sets. Case 3: S={7,11q,13,m,n}S=\{7,11q, 13, m, n\} where m<nm<n and q>1q>1 is odd and m,n7,11q,13m, n \neq 7,11q, 13 Suppose that q=3q=3. This means that mn33mn \leq 33. If m=3m=3, then the possible values of nn are 5 and 9. (Note that n7n \neq 7.) We cannot have n=11n=11 as this would give mnq=99mnq=99 and a product of 99099 which has equal digits AA and BB. We cannot have m5m \geq 5 since this gives mn45mn \geq 45. Suppose that q=5q=5. This means that mn995mn \leq \frac{99}{5}. If m=3m=3, then n=5n=5. As in Case 2, we cannot have q7q \geq 7. Therefore, in this case, there are 3 possible sets. Case 4: S={7,11,13q,m,n}S=\{7,11,13q, m, n\} where m<nm<n and q>1q>1 is odd and m,n7,11,13qm, n \neq 7,11,13q Suppose that q=3q=3. This means that mn33mn \leq 33. If m=3m=3, the possible values of nn are 5 and 9. (Again, n11n \neq 11 in this case.) We cannot have m5m \geq 5 when q=3q=3 otherwise mn45mn \geq 45. If q=5q=5, we can have m=3m=3 and n=5n=5 but there are no other possibilities. As in Cases 2 and 3, we cannot have q7q \geq 7. Therefore, in this case, there are 3 possible sets. Case 5: S={7q,11r,13,m,n}S=\{7q, 11r, 13, m, n\} where m<nm<n and q,r>1q, r>1 are odd and m,n7q,11r,13m, n \neq 7q, 11r, 13 Here, mnqr99mnqr \leq 99. Since q,r>1q, r>1 are odd, then qr9qr \geq 9 which means that mn11mn \leq 11. Since there do not exist two distinct odd integers greater than 1 with a product less than 15, there are no possible sets in this case. A similar argument rules out the products N=7q1113rmnN=7q \cdot 11 \cdot 13r \cdot m \cdot n, N=711q13rmnN=7 \cdot 11q \cdot 13r \cdot m \cdot n, N=7q11r13smnN=7q \cdot 11r \cdot 13s \cdot m \cdot n where q,r,sq, r, s are odd integers greater than 1. Case 6: S={77,13,m,n,}S=\{77,13, m, n, \ell\} where m<n<m<n<\ell and m,n,77,13m, n, \ell \neq 77,13 Note that 77=71177=7 \cdot 11 since we know that NN has divisors of 7 and 11. Here, mn99mn\ell \leq 99. Since mn357=105mn\ell \geq 3 \cdot 5 \cdot 7=105, there are no possible sets in this case, nor using 71437 \cdot 143 or 119111 \cdot 91 in the product or 1001 by itself or multiples of 77,91 or 143. Having considered all cases, there are 15+3+3+3=2415+3+3+3=24 possible sets. Solution 2: We note first that AB0AB=AB1001AB0AB=AB \cdot 1001, and that 1001=1191=117131001=11 \cdot 91=11 \cdot 7 \cdot 13. Therefore, AB0AB=AB71113AB0AB=AB \cdot 7 \cdot 11 \cdot 13. Since AB0ABAB0AB is odd, then BB is odd. Since A0A \neq 0 and ABA \neq B and BB is odd, then we have the following possibilities for the two-digit integer ABAB: 13,15,17,19,21,23,25,27,29,31,35,37,39,41,43,45,47,49,51,53,57,59,61,63,65,67,69,71,73,75,79,81,83,85,87,89,91,93,95,9713,15,17,19,21,23,25,27,29,31,35,37,39,41,43,45,47,49,51,53,57,59,61,63,65,67,69,71,73,75,79,81,83,85,87,89,91,93,95,97. If the integer ABAB is a prime number, then AB0ABAB0AB cannot be written as the product of five different positive integers each greater than 2, since it would have at most four prime factors. Using this information, we can eliminate many possibilities for ABAB from our list to obtain the shorter list: 15,21,25,27,35,39,45,49,51,57,63,65,69,75,81,85,87,91,93,9515,21,25,27,35,39,45,49,51,57,63,65,69,75,81,85,87,91,93,95. Several of the integers in this shorter list are the product of two distinct prime numbers neither of which is equal to 7,11 or 13. These integers are 15=3515=3 \cdot 5 and 51=31751=3 \cdot 17 and 57=31957=3 \cdot 19 and 69=32369=3 \cdot 23 and 85=51785=5 \cdot 17 and 87=32987=3 \cdot 29 and 93=33193=3 \cdot 31 and 95=51995=5 \cdot 19. Thinking about each of these as pqp \cdot q for some distinct prime numbers pp and qq, we have AB0AB=pq71113AB0AB=p \cdot q \cdot 7 \cdot 11 \cdot 13. To write AB0ABAB0AB as the product of five different positive odd integers greater each greater than 2, these five integers must be the five prime factors. For each of these 8 integers (15,51,57,69,85,87,93,95)(15,51,57,69,85,87,93,95), there is 1 set of five distinct odd integers, since the order of the integers does not matter. This is 8 sets so far. This leaves the integers 21,25,27,35,39,45,49,63,65,75,81,9121,25,27,35,39,45,49,63,65,75,81,91. Seven of these remaining integers are equal to the product of two prime numbers, which are either equal primes or at least one of which is equal to 7,11 or 13. These products are 21=3721=3 \cdot 7 and 25=5525=5 \cdot 5 and 35=5735=5 \cdot 7 and 39=31339=3 \cdot 13 and 49=7749=7 \cdot 7 and 65=51365=5 \cdot 13 and 91=71391=7 \cdot 13. In each case, AB0ABAB0AB can then be written as a product of 5 prime numbers, at least 2 of which are the same. These 5 prime numbers cannot be grouped to obtain five different odd integers, each larger than 1, since the 5 prime numbers include duplicates and if two of the primes are combined, we must include 1 in the set. Consider, for example, 21=3721=3 \cdot 7. Here, 21021=377111321021=3 \cdot 7 \cdot 7 \cdot 11 \cdot 13. There is no way to group these prime factors to obtain five different odd integers, each larger than 1. Similarly, 25025=557111325025=5 \cdot 5 \cdot 7 \cdot 11 \cdot 13 and 91091=7137111391091=7 \cdot 13 \cdot 7 \cdot 11 \cdot 13. The remaining three possibilities (35, 49 and 65) give similar situations. This leaves the integers 27,45,63,75,8127,45,63,75,81 to consider. Consider 27027=337111327027=3^{3} \cdot 7 \cdot 11 \cdot 13. There are 6 prime factors to distribute among the five odd integers that form the product. Since there cannot be two 3's in the set, the only way to do this so that they are all different is {3,9,7,11,13}\{3,9,7,11,13\}. Consider 81081=347111381081=3^{4} \cdot 7 \cdot 11 \cdot 13. There are 7 prime factors to distribute among the five odd integers that form the product. Since there cannot be two 3 s or two 9 s in the set and there must be two powers of 3 in the set, there are four possibilities for the set SS: S={3,27,7,11,13},{3,9,21,11,13},{3,9,7,33,13},{3,9,7,11,39}S=\{3,27,7,11,13\},\{3,9,21,11,13\},\{3,9,7,33,13\},\{3,9,7,11,39\}. Consider 45045=3257111345045=3^{2} \cdot 5 \cdot 7 \cdot 11 \cdot 13. There are 6 prime factors to distribute among the five odd integers that form the product. Since two of these prime factors are 3, they cannot each be an individual element of the set and so one of the 3 s must always be combined with another prime giving the following possibilities: S={9,5,7,11,13},{3,15,7,11,13},{3,5,21,11,13},{3,5,7,33,13},{3,5,7,11,39}S=\{9,5,7,11,13\},\{3,15,7,11,13\},\{3,5,21,11,13\},\{3,5,7,33,13\},\{3,5,7,11,39\}. Consider 75075=3527111375075=3 \cdot 5^{2} \cdot 7 \cdot 11 \cdot 13. Using a similar argument to that in the case of 45045, we obtain S={15,5,7,11,13},{3,25,7,11,13},{3,5,35,11,13},{3,5,7,55,13},{3,5,7,11,65}S=\{15,5,7,11,13\},\{3,25,7,11,13\},\{3,5,35,11,13\},\{3,5,7,55,13\},\{3,5,7,11,65\}. Finally, consider 63063=3272111363063=3^{2} \cdot 7^{2} \cdot 11 \cdot 13. There are 6 prime factors to distribute among the five odd integers that form the product. Since we cannot have two 3 s or two 7 s in the product, the second 3 and the second 7 must be combined, and so there is only one set in this case, namely S={3,7,21,11,13}S=\{3,7,21,11,13\}. We have determined that the total number of sets is thus 8+1+4+5+5+1=248+1+4+5+5+1=24.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.