Competition problem — Number theory

Library / /293 of 377

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:
You are given a set of cards labeled from $1$ to $100$ . You wish to make piles of three cards such that in any pile, the number on one of the cards is the product of the numbers on the other two cards. However, no card can be in more than one pile. What is the maximum number of piles you can form at once?

Solution

Solution: $8$
Certainly, the two factors in any pile cannot both be at least $10$ , since then the product would be at least $10 \times 11 > 100$ . Also, the number $1$ can not appear in any pile, since then the other two cards in the pile would have to be the same. So each pile must use one of the numbers $2, 3, \ldots, 9$ as one of the factors, meaning we have at most $8$ piles. Conversely, it is easy to construct a set of $8$ such piles, for example:
$\begin{array}{llll} \{9, 11, 99\} & \{8, 12, 96\} & \{7, 13, 91\} & \{6, 14, 84\} \\ \{5, 15, 75\} & \{4, 16, 64\} & \{3, 17, 51\} & \{2, 18, 36\} \end{array}$

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.