Maths Olympiad Prep

Library / Mathematical Olympiad in Ukraine /17 of 27

Mathematical Olympiad in Ukraine

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 48a⋅48b⋅48c⋅48d=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 n≥mn \ge m. But also we have the subset {1,2,24,48}\{1, 2, 24, 48\} which has product of elements 1⋅2⋅24⋅48=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.

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.