Maths Olympiad Prep

Library / South African Mathematics Olympiad /31 of 48

South African Mathematics Olympiad

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
0≤a≤1,0≤b≤2,0≤c≤2,0≤d≤1,0≤e≤3, 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+e≥2a+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 144−1−5=138144 - 1 - 5 = 138.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.