Question

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

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

Answer

Solution:

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

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

Hence the smallest such $m$ is $243.$

2010 AIME I Problem 12

Solution:

Problem 12 in Other Years