Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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\).
Mark Hennings · 2 months, 3 weeks ago

Log in to reply

@Pi Han Goh @Mark Hennings Kartik Sharma · 2 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...