Mock AIME II 2012 Problems/Problem 10

Problem

Call a set of positive integers $\mathcal{S}$ $\textit{lucky}$ if it can be split into two nonempty disjoint subsets $\mathcal{A}$ and $\mathcal{B}$ with $A\cup B=S$ such that the product of the elements in $\mathcal{A}$ and the product of the elements in $\mathcal{B}$ sum up to the cardinality of $\mathcal{S}$. Find the number of $\textit{lucky}$ sets such that the largest element is less than $15$. (Disjoint subsets have no elements in common, and the cardinality of a set is the number of elements in the set.)

Solution

Let the cardinality of $\mathcal{S}$ be $n$. We therefore want the sum of the products of the elements of $\mathcal{A}$ and $\mathcal{B}$ to be $n$, and this is constant no matter what the elements of $\mathcal{S}$ are. The set with the smallest such sum of products is the set $\{1, 2, \cdots n\}$, since if one of the elements is not in this set, then we can replace it with one of the elements in this set and get a smaller product. However, notice that whichever subset $\mathcal{A}$ or $\mathcal{B}$ contains the element $n$, then the product of the elements of that set will be greater than or equal to $n$, and the product of the elements of the other set will be positive, and so the sum of the products must be greater than $n$. Therefore, no lucky set of positive integers is possible and the answer is $\boxed{000}$.