Olympiad Maths Prep

Library / /18 of 28

Combinatorics Difficulty 5.8 AIME, harder Prove it Ukraine

Consider the set M={1,2,3,4,6,8,12,16,24,48}M = \{1,2,3,4,6,8,12,16,24,48\} and all of its four-element subsets. Denote by nn the number of these subsets such that the product of their elements is greater than 20092009 and by mm the number of these subsets such that the product of their elements is smaller than 20092009. Which number is bigger - nn or mm?

Solution

Let M1={a,b,c,d}M_1 = \{a, b, c, d\} be a four-element subset of MM such that abcd<2009abcd < 2009. Then the subset M2={48a,48b,48c,48d}M_2 = \{\frac{48}{a}, \frac{48}{b}, \frac{48}{c}, \frac{48}{d}\} is also a four-element subset of MM because all of its elements are distinct and belong to MM and 48a48b48c48d=484abcd>4842009>2009\frac{48}{a} \cdot \frac{48}{b} \cdot \frac{48}{c} \cdot \frac{48}{d} = \frac{48^4}{abcd} > \frac{48^4}{2009} > 2009. It follows that nmn \ge m. But also we have the subset {1,2,24,48}\{1, 2, 24, 48\} which has product of elements 122448=482>20091 \cdot 2 \cdot 24 \cdot 48 = 48^2 > 2009 and doesn't have any corresponding pair with product of elements less than 20092009. Thus n>mn > m.

Looking for a route rather than 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.