Competition problem — Combinatorics

Library / /38 of 71

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
How many different numbers are obtainable from five 5s by first concatenating some of the 5s, then multiplying them together? For example, we could do $5 \cdot 55 \cdot 55,555 \cdot 55$ , or $55555$ , but not $5 \cdot 5$ or $2525$ .

Solution

Solution:
Answer: $7$

If we do $55555$ , then we're done.

Note that $5$ , $55$ , $555$ , and $5555$ all have completely distinguishable prime factorizations. This means that if we are given a product of them, we can obtain the individual terms. The number of $5555$ 's is the exponent of $101$ , the number of $555$ 's is the exponent of $37$ , the number of $55$ 's is the exponent of $11$ minus the exponent of $101$ , and the number of $5$ 's is just whatever we need to get the proper exponent of $5$ .

Then the answer is the number of ways we can split the five $5$ 's into groups of at least one. This is the number of unordered partitions of $5$ , which is $7$ .

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 reproduced verbatim; metadata (topic, difficulty) added by this project.