2001 USA TST Problems/Problem 9

Revision as of 19:39, 23 April 2008 by Boy Soprano II (talk | contribs) (problem and solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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$

Combining the statments of Lemmata 1 and 2, we are done. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources