Maths Olympiad Prep

Library / /100 of 101

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Estonia

In how many ways can one choose 5 numbers from the list
18,17,16,15,14,13,12,1,2,3,4,5,6,7,8\frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, 1, 2, 3, 4, 5, 6, 7, 8
so that the product of the chosen numbers is 1?

Remark: Two choices are considered different if one choice contains a number that the other choice does not. The order of numbers is not important.

Solutions — 2

Solution 1

Let's first count the choices that include the number 11. If some three of the remaining numbers were 22, 33, and 44, then the conditions of the problem would be violated, because the denominators of all the fractions in the list are smaller than 234=242 \cdot 3 \cdot 4 = 24, and the product of the selected 5 numbers could not be 11. If instead of 22, 33, and 44 some other 3 integers are chosen, their product will be even larger, so the conditions of the problem cannot be met. The situation is similar if 3 fractions are chosen next to the number 11. Thus, in addition to the number 11, the choice must include 2 integers and 2 fractions, with the product of the integers equal to the product of the denominators of the fractions. There are exactly 21 ways to choose 2 integers in addition to the number 11, and the resulting products are in the following table:

345678
26810121416
31215182124
420242832
5303540
64248
756

We see that the numbers 1212 and 2424 appear in the table 2 times, the remaining numbers are unique. Thus, we get 21 options where the selected integers are the same as the denominators of the selected fractions, and in addition 4 options where the selected integers and the denominators of the selected fractions are not the same, but their product is either 1212 or 2424. In total, there are 25 options with the number 11.

Now we count the options that do not have the number 11. We have to choose either 3 integers and 2 fractions or 3 fractions and 2 integers. Since, due to symmetry, there are the same number of options of both types, we count the options involving 3 integers and 2 fractions. If 22 were not included in the selection, the product of the selected integers should be at least 345=603 \cdot 4 \cdot 5 = 60, but according to the multiplication table, the product of the denominators of any 2 fractions is less than 6060, which is why the condition of the problem cannot be met. Therefore, 22 must be included in the selection. Similarly, we see that either 33 or 44 must also be included in the selection. We get the possibilities
234=24,235=30,236=36,237=42,238=48,245=40,246=48,247=56,248=64. 2 \cdot 3 \cdot 4 = 24, \quad 2 \cdot 3 \cdot 5 = 30, \quad 2 \cdot 3 \cdot 6 = 36, \quad 2 \cdot 3 \cdot 7 = 42, \quad 2 \cdot 3 \cdot 8 = 48, \\ 2 \cdot 4 \cdot 5 = 40, \quad 2 \cdot 4 \cdot 6 = 48, \quad 2 \cdot 4 \cdot 7 = 56, \quad 2 \cdot 4 \cdot 8 = 64.
Of these 9 products, only 3636 and 6464 do not appear in the multiplication table above, the product 2424 appears there 2 times and the remaining 6 products 1 time. So we get 20+12+61=82 \cdot 0 + 1 \cdot 2 + 6 \cdot 1 = 8 possibilities. There are the same number of possibilities with 3 fractions and 2 integers. So there are 28=162 \cdot 8 = 16 possibilities without the number 11.
Hence the total number of possibilities is 25+16=4125 + 16 = 41.

Solution 2

The list of numbers contains 7 pairs of reciprocals in the form (1a,a)(\frac{1}{a}, a). At most 2 such pairs can occur among the 5 numbers chosen.
If there are two pairs of reciprocals in the choice, then the last number must be 11. To choose 2 pairs from the 7 existing pairs of reciprocals, there are 762=21\frac{7 \cdot 6}{2} = 21 possibilities.
If there is one pair of reciprocals in the choice, then the product of the remaining 3 numbers must be 11. If the integers aa and bb are among these 3 numbers, then the last number must be 1ab\frac{1}{ab}, so the integer abab is also in the original list. Similarly if the fractions 1a\frac{1}{a} and 1b\frac{1}{b} are among these 3 numbers, then aa, bb and abab must be in the original list. The only such numbers are 22, 33, 66 and 22, 44, 88, each of which gives 2 choices for the 3 numbers from the original list. Then there are 73=47 - 3 = 4 options for the pair of reciprocal numbers. So in this case there are 224=162 \cdot 2 \cdot 4 = 16 possibilities.
If there are no pairs of reciprocals in the selection, then each integer can appear in the selection at most once, either by itself or in the denominator of the reciprocal. The prime numbers 55 and 77 cannot appear in either role. The prime number 33 only appears as a factor in the numbers 33 and 66; if both of them were omitted, there would not be enough numbers left in the selection, so they must both be in the selection, either as 13\frac{1}{3} and 16\frac{1}{6} or as 29\frac{2}{9} and 23\frac{2}{3}. The product of these numbers is 12\frac{1}{2} or 22, respectively. The remaining numbers are 11, 22, 44, and 88, from which 3 must be chosen. If one does not choose 11, then it is not possible to get the number 22 or 12\frac{1}{2} by using each remaining number or its reciprocal as a factor only once. Thus, the number 11 must be in the selection. From the remaining numbers and their reciprocals, the number 22 or 12\frac{1}{2} can be composed in 4 ways: 124\frac{1}{2} \cdot 4, 148\frac{1}{4} \cdot 8, 2142 \cdot \frac{1}{4}, and 4184 \cdot \frac{1}{8}. So the total number of choices is 21+16+4=4121 + 16 + 4 = 41.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.