Maths Olympiad Prep

Library / /2 of 8

Combinatorics Difficulty 4.0 AIME Find the answer Italy

Problem:

In a box there are twenty balls numbered from 1 to 20. Each number appears on one and only one of these balls. What is the minimum number of different balls we must draw, in order to be sure that the product of their numbers is a multiple of 12?

Pick one

Solution

Solution:

The answer is (D). The multiples of 3 between 1 and 20 are 6, so there are 14 numbers that are not multiples of 3. If we were to draw exactly those 14 numbers, their product would not be a multiple of 3, and even less of 12, so the minimum number nn of draws needed to ensure that the product is a multiple of 12 is greater than 14. If instead we draw 15 numbers, we will certainly have at least one multiple of 3. Since the even numbers between 1 and 20 are 10, and the odd ones are 10, with 15 draws we are guaranteed at least 5 even numbers. Thus the product will be a multiple of 3 and a multiple of 25=322^{5}=32. In particular, it will be a multiple of 3 and of 4, and hence of 12. It follows that nn is exactly 15.

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 translated into English from it; metadata (topic, difficulty) added by this project.