2001 USA TST Problems/Problem 9

Problem

(Zuming Feng) Let $A$ be a finite set of positive integers. Prove that there exists a finite set $B$ of positive integers such that $A \subseteq B$ and $\prod_{x\in B} x = \sum_{x\in B} x^2.$

Solution

Lemma 1. For any finite set $A$ of positive integers, there exists a finite set $C$ of positive integers such that $A \subseteq C$ and $\prod_{x \in C} x \ge \sum_{x\in C} x^2$ .

Proof. Let us abbreviate $p = \prod_{x\in A}x$ and $s = \sum_{x\in A} x^2$ . Suppose that $p < s$ (otherwise, we may have $C=A$ ). Let $a$ be a positive integer larger than $\max(s,5)$ (and thus larger than any element of $A$ ). Taking $C = A \cup \{a, a+1, a+2\}$ , evidently $A \subseteq C$ , and $\begin{align*} \prod_{x\in C} x &= pa(a+1)(a+2) > pa (a+1)^2 > 5(a+1)^2 \\ &> s + a^2 + (a+1)^2 + (a+2)^2 = \sum_{x \in C} x, \end{align*}$ as desired. $\blacksquare$

Lemma 2. For any finite set $C$ of positive integers such that $\prod_{x \in C} x \ge \sum_{x\in C} x^2$ , there exists a finite set $B$ of positive integers such that $C \subseteq B$ and $\prod_{x\in B}x = \sum_{x\in B} x^2 .$

Proof. Let us abbreviate $s = \sum_{x \in C}x^2$ , and $d = \prod_{x \in C} x - \sum_{x \in C} x^2$ . We induct on the quantity $d$ , which by hypothesis is a nonnegative integer.

For our base case, $d=0$ , we may take $B=C$ .

Now suppose that the lemma holds for $d<k$ . Suppose $d=k$ . Let $C' = C \cup \{s+k-1\}$ . Then $\prod_{x\in C'} x - \sum_{x\in C'}x^2 = (s+k)(s+k-1) - s - (s+k-1)^2 = k-1,$ so by inductive hypothesis, there exists a set $B$ such that $C' \subseteq B$ and $\prod_{x\in B} x = \sum_{x\in B} x^2 .$ Since $C \subseteq C' \subseteq B$ , this set $B$ satisfies the lemma's conditions. $\blacksquare$