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
Small Hint:

Try two-subset partitions that keep small numbers and their pairwise products apart, such as separating {3,,8}\{3, \ldots, 8\} from {9,,80}\{9, \ldots, 80\}

Big Hint:

For the upper bound, follow the powers of 3:3: once 33 and 99 are forced into different subsets, place 2727 and 81,81, and one more power creates a contradiction

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