Maximal Products of a Given Sum

Back in high school, I came across the following contest problem:

Question: Let $S$ be a set of positive integers totaling 20. What is the maximum value of

$\displaystyle\prod_{x \in S} x$

It’s a fun problem, so don’t rush past the spoiler tags too fast. When you’re ready, I’ll spoil the solution to the question above, and discuss a “continuous” version of the question above. Namely, what happens when $S$ is allowed to include positive real numbers?

As promised, here’s one solution to the question posed before the break:

Solution: Suppose that $S$ is a set of positive integers totaling 20. If for some $x \in S$ we have $x > 4$ , then we increase our product over terms in $S$ by replacing $x$ by the two elements $2$ and $x-2$ . We may therefore conclude that $x \in S$ is at most 4. In fact, we may assume without loss of generality that $x \in S$ is at most 3, since any occurrence of 4 may just as easily be the pair {2,2}.

From the other direction, we may assume that $x > 1$ for all $x \in S$ , since

$1\cdot x_1 \cdots x_k < (x_1 +1)\cdot x_3 \cdots x_k.$

In other words, the set $S$ that maximizes our product consists (without loss of generality) of just 2’s and 3’s. Moreover, the inequality

$2 \cdot 2 \cdot 2 < 3 \cdot 3$

tells us that 2 occurs in our maximal product at most twice. The set $S$ is then determined uniquely, as

$S=\{2,3,3,3,3,3,3\}.$

For this set, our product is 1458, and this product is maximal. $\square$

Older readers may recognize this solution from an earlier post, where it was used to produce a crude upper bound on the maximal orders of elements in the permutation group $S_n$ . We won’t be heading back down that path today. Rather, let’s turn to the following, continuous analogue of our earlier question:

Question: Let $S$ be a set of positive real numbers totaling $n > 1$ . What is the maximal product of the set $S$ , as $S$ varies?

If we want to follow the discrete case, we quickly prove that in a maximal set we may assume that $x \in S$ implies

$x \in (1,4)$ .

However, unlike in the discrete case, this leaves a spectrum of possibilities. Is it obvious, for example, that our product should be bounded? Could an optimal solution have infinitely many terms in $S$ ?

As it happens, neither of these pathologies arise, because an infinite product either has

Product equal to zero, or
Infinitely many terms that do not limit to zero, which contradicts our restriction on the sum of $S$ .

With that worry at ease, we present our solution to the continuous case:

Solution: Our solution uses the general idea of perturbation theory: if $x_1,x_2$ are both in $S$ , let’s consider what happens when we replace the pair $x_1,x_2$ with its arithmetic mean $(x_1+x_2)/2$ , occurring twice. Since

$\left(\frac{x_1+x_2}{2}\right)^2 \geq x_1x_2 \quad \Leftrightarrow \quad \mathrm{AM}(x_1^2,x_2^2) =\frac{x_1^2+x_2^2}{2} \geq x_1x_2 = \mathrm{GM}(x_1^2,x_2^2),$

and this latter inequality follows from the AM-GM inequality, it follows that we can always increase our product by averaging out the terms in $S$ . In a set $S$ with maximal product, we may assume that every term in $S$ is equal. If $S$ has $m$ terms, then

$S = \{n/m,\ldots,n/m\}$ ,

and the product over $S$ is $(n/m)^m$ .

For which integer $m$ is this maximized? Let $t=n/m$ ; then we seek to maximize

$(n/m)^m=t^{n/t}=\left(t^{1/t}\right)^n$ ,

with $t$ an integer multiple of $1/m$ . If we relax our assumptions on $t$ and merely assume that $t > 0$ is real, then $t^{1/t}$ (and hence $(t^{1/t})^n$ ) is uniquely maximized for $t=e$ . Therefore, restricting to $t \in n/\mathbb{Z}$ , our maximum is attained at one of the following two points:

$t=n/\lfloor n/e \rfloor, \quad n/\lceil n/e \rceil$ ,

which in either case gives us the maximal product

$\max\left(\left(\frac{n}{\lfloor n/e \rfloor}\right)^{\lfloor n/e \rfloor},\left(\frac{n}{\lceil n/e \rceil}\right)^{\lceil n/e \rceil}\right).\quad\qquad\qquad\qquad (1)$

So, which one of the terms above is largest? Based on the work that got us this far, it stands to reason that our answer should correlate (if not correspond) to whichever one of the two approximations

$\frac{n}{\lfloor n/e \rfloor}, \qquad \frac{n}{\lceil n/e \rceil}$

is closer to $e$ . Indeed, if the function we were maximizing — namely $x^{n/x}$ — was symmetric about its unique maximum, our answer would be this simple: take the choice that corresponds to the better approximation. While this claim fails, our intuition in the matter nevertheless carries through.

We can prove the following result, which says that each choice in the maximum from line (1) occurs with equal probability:

Theorem: The set of integers such that the maximum in line (1) occurs with the first term has natural density 1/2.

Proof: For any $\alpha <1/2$ , there exists a positive $\epsilon >0$ such that

$(1+\epsilon)\left(\frac{\alpha}{n}\right)^2 \leq (1-\epsilon)\left(\frac{1-\alpha}{n}\right)^2,$

for all integers $n$ . Let $\delta_n = \{n/e\}$ , in which $\{x\}$ denotes the fractional part of the real number $x$ , and let $S_\alpha$ denote the set of integers

$S_\alpha = \{n \in \mathbb{N} : \{n/e\}<\alpha\}.$

It follows that

$e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1+\epsilon)\left(\frac{\delta_n}{n}\right)^2 \geq e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1-\epsilon)\left(\frac{1-\delta_n}{n}\right)^2$

for all $n \in S_\alpha$ . Expanding $f(x):=x^{-x}$ in a power series at $x=1/e$ , we find

$f(x)=e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}\left(x-\frac{1}{e}\right)^2+O\left(\left(x-\frac{1}{e}\right)^3\right).$

Therefore, there exists an interval $I_\epsilon$ such that for all $x \in I_\epsilon$ , we have

$e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1+\epsilon)\left(x-\frac{1}{e}\right)^2 \leq f(x) \leq e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1-\epsilon)\left(x-\frac{1}{e}\right)^2.$

Provided that $n \in S_\alpha$ is taken large enough so that both $\frac{1}{e}-\frac{\delta_n}{n}$ and $\frac{1}{e}+\frac{1-\delta_n}{n}$ both lie in the interval $I_\epsilon$ , we find that

$f\left(\frac{1}{e}-\frac{\delta_n}{n}\right) \geq f\left(\frac{1}{e}+\frac{1-\delta_n}{n}\right). \qquad\qquad\qquad\qquad (2)$

Thus (2) holds on a set of natural density equal to the natural density of the set $S_\alpha$ . But $S_\alpha$ has natural density $\alpha$ , by the equidistribution theorem, which gives (2) on a set of density $\alpha$ for any $\alpha <1/2$ . Conversely, one may show that

$\delta_n >\frac{1}{2} \quad \Longrightarrow \quad f\left(\frac{1}{e}-\frac{\delta_n}{n}\right) < f\left(\frac{1}{e}+\frac{1-\delta_n}{n}\right)\quad\qquad\qquad (3)$

(see the Exercises), which implies that (2) fails for a set of natural density 1/2. Since (2) holds for $n$ if and only if the first term in line (1) is maximal, which gives our result. $\square$

— EXERCISES —

Exercise: If $S$ is a set of positive rationals totaling $n$ , what is the maximal product over the elements in $S$ ?

Exercise: Use the degree two Taylor expansion of $x^{-x}$ about the point $x= 1/e$ to show that the claim in line (3) holds.

Exercise: Show that the interval $I_\epsilon$ can be explicitly bounded from inside, and use this (plus the effective equidistribution theorem) to give an effective version of our final theorem. (Hard.)

a. w. walker

mathematics and miscellany

Maximal Products of a Given Sum

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply