×

# Maximize the integral product

Given $$a_i \in \mathbb{Z}^+ \forall 1\le i \le n$$, and

$$a_1 + a_2 + \cdots + a_n = m$$, where $$m$$ is given positive integer and

$$a_1 a_2 \cdots a_n$$ is maximum.

Find $$a_i, n$$ for a given integer $$m$$.

Note by Kartik Sharma
2 months, 3 weeks ago

Sort by:

Note that $$2(k-2) > k$$ for $$k > 4$$, that $$k+1 > k\times1$$ for $$k \ge 1$$, and that $$3^2 > 2^3$$.

Firstly, note that there are finitely many ways of writing $$m$$ as a sum of positive integer (there are at most $$m$$ integers in the sum, and each is no greater than $$m$$). Thus there certainly is a maximum possible product over all such sums (since there are only finitely many products to consider).

• If one of the numbers $$a$$ in a decomposition of $$m$$ is greater than $$4$$, then we can replace $$a$$ by $$2$$ and $$a-2$$, obtaining a new decomposition of $$m$$ with a larger product. Thus there are no integers greater than $$4$$ in the decomposition of $$m$$ that yields the maximum product.
• If one of the numbers $$a$$ in a decomposition of $$m$$ is equal to $$1$$, another number in the decomposition is equal to $$b$$, replacing the pair of numbers $$a=1,b$$ by the single number $$b+1$$ yields a new decomposition of $$m$$ with a larger product. Thus there are no integers equal to $$1$$ in the decomposition of $$m$$ that yields the maximum product.
• Since $$4 = 2+2=2\times2$$, any copy of the integer $$4$$ can be replaced with two copies of $$2$$, so there is no need for any decomposition of $$m$$ to contain the number $$4$$.

Thus the decomposition of $$m$$ that yields the maximum product contains only the numbers $$2$$ and $$3$$. Since $$2^3 < 3^2$$ and $$2+2+2=3+3$$, any set of three $$2$$s can be replaced by two $$3$$s, resulting in a larger product. Thus the decomposition of $$m$$ that yields the maximum product cannot have more than two $$2$$s.

• If $$m = 3k$$, the only way we can satisfy all the above requirements for a decomposition (only $$2$$s and $$3$$s, and at most two $$2$$s) is to have $$k$$ copies of $$3$$, making the maximum product $$3^k$$.
• If $$m = 3k+1$$, the only way to satisfy these rules is to have two $$2$$s and $$k-1$$ copies of $$3$$, making the maximum product $$2^2 \times 3^{k-1}$$.
• If $$m = 3k+2$$ we are forced to have just one $$2$$ and $$k$$ copies of $$3$$, making the maximum product $$2\times3^k$$.
· 2 months, 3 weeks ago