2010 AIME I Problem 12

Attempt Problem 12 of the 2010 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2010 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Let m3m \ge 3 be an integer and let S={3,4,5,,m}.S = \{3, 4, 5, \ldots, m\}. Find the smallest value of mm such that for every partition of SS into two subsets, at least one of the subsets contains integers a,a, b,b, and cc (not necessarily distinct) such that ab=c.ab = c.

Note: a partition of SS is a pair of sets A,A, BB such that AB=A \cap B = \emptyset and AB=S.A \cup B = S.

Answer: 243
Concepts:logical deductionextremal argument
Difficulty rating: 3060
Solution:

First, m=243m = 243 works. Suppose S={3,4,,243}S = \{3, 4, \ldots, 243\} were partitioned into TT and UU with neither containing a product, and say 3T.3 \in T. Then 9=339 = 3 \cdot 3 must lie in U,U, so 81=9981 = 9 \cdot 9 must lie in T,T, and then 243=381243 = 3 \cdot 81 must lie in U.U. Now consider 27:27: if 27T,27 \in T, then 327=813 \cdot 27 = 81 puts a product in T;T; if 27U,27 \in U, then 927=2439 \cdot 27 = 243 puts one in U.U. Either way we reach a contradiction.

For m=242,m = 242, the partition T={3,,8}{81,,242}T = \{3, \ldots, 8\} \cup \{81, \ldots, 242\} and U={9,,80}U = \{9, \ldots, 80\} avoids products: two elements of {3,,8}\{3, \ldots, 8\} multiply to something in [9,64]U,[9, 64] \subseteq U, any product involving an element of {81,,242}\{81, \ldots, 242\} is at least 381=243>242,3 \cdot 81 = 243 \gt 242, and two elements of UU multiply to at least 81>80.81 \gt 80.

Hence the smallest such mm is 243.243.

← Problem 11#11
Full Exam

Problem 12 in Other Years