Solution for February 2011

The Problem:
	For which positive integers $n$ and $a_1, a_2, a_3, \dots, a_n$ is the product $a_1\cdot a_2 \cdot a_3 \cdot \dots \cdot a_n$ as large as possible when these numbers must satisfy $a_1 + a_2 + a_3 + \dots + a_n = 2011$?

Correct responses:

Answer. The maximum product is achieved in two ways: with $\mathbf{n=670}$ using 669 factors of 3 and one of 4, and with $\mathbf{n=671}$ using 669 factors of 3 and two of 2. Correct solutions to the January problem were submitted by Lou Cairoli (USA) Bernard Collignon (France) Mei-Hui Fang (Austria) Philippe Fondanaiche (France) Bruce Golfman (Austria) Gruian Cornel (Romania) Verena Haider (Austria Benoît Humbert (France) Ile Ilijevski (Macedonia) Kipp Johnson (USA) Wolfgang Kais (Germany) Normand LaLiberté Matthew Lim (USA Patrick J. LoPresti (USA) John T. Robinson (USA) Mathias Schenker (Switzerland) Heri Setiyawan (Indonesia) Albert Stadler (Switzerland) Paul Voyer (France)   In addition we received several submissions that provided answers without satisfactory explanations. Please remember that we are looking for solutions, not just answers. A complete solution explains where the answer comes from and why it is correct.

The solution:

Because there are finitely many collections of positive integers whose sum is 2011, at least one of them must achieve the maximum product. Suppose that $a_1, a_2, a_3, \dots, a_n$ is the collection we seek; that is, the product $a_1\cdot a_2 \cdot a_3 \cdot \dots \cdot a_n$ is as large as possible among all collections of integers for which $a_1 + a_2 + a_3 + \dots + a_n = 2011$.

• $n>1$, otherwise $a_1 = 2011$ and the "product" of this one item, namely 2011, is clearly not the maximum; indeed, any collection of two or more integers greater than 1 that sum to 2011 produces a product greater than 2011.
  
  
• None of the $a_i$ can be 1; otherwise we could remove it from our collection and replace some $a_j, \; j\ne i,$ by $a_j+1$, keeping the sum at 2011 but increasing the product.
  
  
• None of the $a_i$ can be 5 or larger: should, to the contrary, $a_i \ge 5$ then we could adjoin 2 to our collection and replace $a_i$ by $a_i - 2$, keeping the sum at 2011 and increasing the product (because $2(a_i-2) = 2a_i-4 > a_i$ when $a_i>4$).

We deduce that the $a_i$'s in the maximum product must equal 2, 3, or 4. In addition, in the maximum product

• there cannot be more than two 2s (because if three of the $a_i$'s were to equal 2, they could be replaced by a pair of 3s ($2+2+2 = 3+3$) and the resulting product would increase ($3\cdot 3 > 2\cdot2\cdot2$)).
  
  
• there cannot be more than one 4 (because a pair of 4s could be replaced by two 3s and a 2, which would fix the sum but increase the product), and
  
  
• there cannot be both a 4 and a 2 (because they could be replaced by two 3s, fixing the sum but increasing the product).

In summary, we want our collection to contain as many 3s as possible, adjoining either 2s or a 4 as needed to add up to 2011. Since $$2011 = 3\cdot670+1 = 3\cdot669+4= 3\cdot669+ 2\cdot2,$$
we must use 669 3s and either one 4 or two 2s to obtain the greatest product. For the record, the maximum product is therefore

$4\cdot 3^{669} = 2^2\cdot 3^{669} =$

62543099305847562773534559385871455301508139470863726047575631380014821
18438409353294154032227959155893025699392054258970035198055096949397313
10493989960203598356927645249925489567206575014415623015699165339810785
06999696445932185061281385497889404585595814417259978814911519620863137
698556067203931868434684932884205132
$\approx6.25\times10^{319}$.

We thank Lou Cairoli and Jim Altieri who independently sent us the product --- no doubt at a cost of numerous worn-out pencils.

Further comments. Several participants observed that the same argument works as well for any number $S > 1$ in place of 2011; specifically, the maximum product of any collection of numbers whose sum is $S = 3k + j, \; j = 0, 1, 2$, is

$3^k$ when $j=0$,
$2^2\cdot 3^{k-1} = 4 \cdot 3^{k-1}$ when $j=1$, and
$2 \cdot3^k$ when $k=2$.

A few correspondents investigated what happens when given a collection of $n$ positive real numbers $a_i$ whose sum is 2011 (instead of $n$ positive integers), and asked to describe the collection whose product is a maximum. The arithmetic-geometric inequality implies that the product of the $a_i$'s is maximized when $a_i = x$ for all $i$ and some fixed real number $x$. We, therefore, in the continuous version of the problem wish to find the value of $x$ that maximizes $f(x) = x^\frac{2011}{x}$. Those of us who have seen enough calculus will know that $f(x)$ achieves its maximum value when $x=e$. The number of terms is then somewhere around $\frac{2011}{e} \approx \frac{2011}{2.718} \approx 739.9$. Direct computation of $\left(\frac{2011}{739}\right)^{739}$ and $\left(\frac{2011}{740}\right)^{740}$ (using logarithms) says that the maximum product is attained with $a_i = \frac{2011}{740}$ for all $i$. This leads to the maximum product $\left(\frac{2011}{740}\right)^{740}\approx 1.97 \times 10^{321}$, which is a bit larger than in the solution to our original problem. Some correspondents then tried to deduce from the real-number problem that setting as many $a_i$ as possible equal to the integer closest to $e$, namely 3, would indeed solve the original problem. That might be the case, but nobody supplied a convincing argument that the answer to our original problem follows directly from the calculus result.