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

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

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 is allowed to include positive real numbers?

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

*Solution: *Suppose that is a set of positive integers totaling 20. If for some we have , then we increase our product over terms in by replacing by the two elements and . We may therefore conclude that is at most 4. In fact, we may assume without loss of generality that 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 for all , since

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

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

For this set, our product is 1458, and this product is maximal.

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 . 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 be a set of positive real numbers totaling . What is the maximal product of the set , as varies?

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

.

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 ?

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 .

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

*Solution: *Our solution uses the general idea of perturbation theory: if are both in , let’s consider what happens when we replace the pair with its arithmetic mean , occurring twice. Since

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 . In a set with maximal product, we may assume that every term in is equal. If has terms, then

,

and the product over is .

For which integer is this maximized? Let ; then we seek to maximize

,

with an integer multiple of . If we relax our assumptions on and merely assume that is real, then (and hence ) is uniquely maximized for . Therefore, restricting to , our maximum is attained at one of the following two points:

,

which in either case gives us the maximal product

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

is closer to . Indeed, if the function we were maximizing — namely — 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 , there exists a positive such that

for all integers . Let , in which denotes the fractional part of the real number , and let denote the set of integers

It follows that

for all . Expanding in a power series at , we find

Therefore, there exists an interval such that for all , we have

Provided that is taken large enough so that both and both lie in the interval , we find that

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

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

**— EXERCISES —**

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

**Exercise: **Use the degree two Taylor expansion of about the point to show that the claim in line (3) holds.

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

## 2 comments

Comments feed for this article

June 4, 2016 at 11:44 pm

jeremyI’m confused about the first solution. Aren’t elements of a set supposed to be unique? As in, how can you have several 3’s in the same set?

June 6, 2016 at 2:08 am

Alexander WalkerTechnically, yes. In this article I’m actually talking about multisets. You can ask this same question about sets (in the strict sense), but the analysis is a bit harder.