Maths Olympiad Prep

Library / /43 of 60

Combinatorics Difficulty 4.6 AIME Prove it South Africa

How many different numbers can be written as the product of two or more of the numbers 33, 44, 55, 66, 77, 77, 77?

Solution

The required numbers are of the form 3a4b5c6d7e3^a4^b5^c6^d7^e, where
0a1,0b2,0c2,0d1,0e3, 0 \le a \le 1, \quad 0 \le b \le 2, \quad 0 \le c \le 2, \quad 0 \le d \le 1, \quad 0 \le e \le 3,
and a+b+c+d+e2a+b+c+d+e \ge 2. This gives two possible values of aa, three of bb, three of cc, two of dd, and four of ee, making a total of 2×3×3×2×4=1442 \times 3 \times 3 \times 2 \times 4 = 144 possible numbers if we ignore the last restriction. To satisfy it, we must exclude one possibility with a+b+c+d+e=0a+b+c+d+e = 0 and five possibilities with a+b+c+d+e=1a+b+c+d+e = 1, so the final total is 14415=138144 - 1 - 5 = 138.

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.