7
$\begingroup$

The sum of a set of positive integers = $2008$.

$a_1+a_2+…+a_n=2008$ where all $a_i$ are positive integers.

If $A_k=a_1 a_2 … a_k$ , what is the largest possible value of $A_1+A_2+…+A_n$ ?

$\endgroup$
8
  • 1
    $\begingroup$ Here's a tutorial in MathJax $\endgroup$ Commented Jun 9, 2017 at 19:19
  • $\begingroup$ So there can be duplicates? $\endgroup$
    – Mr. Xcoder
    Commented Jun 9, 2017 at 19:23
  • $\begingroup$ Yes, duplicates are allowed $\endgroup$
    – ramana_k
    Commented Jun 9, 2017 at 19:24
  • $\begingroup$ What have you looked at? If you drop the condition that the $\{a_i\}$ are all integral then I expect the maximum for a fixed $n$ is realized when all of them are equal, and that if if you maximize over $n$ you want $n\approx \frac {2008}e$ so something like $n=739$. Not clear to me how to cope with integrality. I mean, you could take $530$ threes and $209$ twos but I have no idea if that is optimal. $\endgroup$
    – lulu
    Commented Jun 9, 2017 at 19:41
  • $\begingroup$ Having not put much thought into it yet, an observation I make is that $A_1+A_2+\dots+A_n = a_1(1+a_2(1+a_3(1+a_4(\dots (1+a_n))\dots)$. This might or might not be a helpful observation $\endgroup$
    – JMoravitz
    Commented Jun 9, 2017 at 19:41

1 Answer 1

6
$\begingroup$

All of the $a_i$ must come in weakly decreasing order.

If $a_1+\dots+a_n=2008$ with $a_1$ an even number bigger than $2$, then consider $$(a_1/2)+2+a_2+\dots+a_n+1+\dots+1=2008.$$ If $a_1+\dots+a_n=2008$ with $a_1$ odd and at least $5$, say $a_1=2k+1$, consider $$ (a_1-2)+2+a_2\dots+a_n=2008 $$ (Clearly $a_1=1$ cannot be maximal). Once you have figured out $a_1$, apply the same argument to $a_2$, $a_3$, etc. (edit: at each step above, replace $j$ trailing copies of $1$ by the integer $j$; that is, instead of using $2006+1+1$, use $2006+2$. Doing this does not change the result).

This shows that each $a_i$ must be $3$ or $2$. Simplifying the terms $A_1+\dots+A_n$ is now just adding terms of a 2 geometric series. Finally, if there are $k$ $3s$ then there are $\frac{2008-3k}{2}$ $2s$; thus we want to maximize $$ \frac{3(3^k-1)}{2}+\frac{3(3^k-1)}{2}\cdot2\cdot\left(2^\frac{2008-3k}{2}-1\right) $$ From Wolframalpha this gives $668$ copies of $3$ and $2$ copies of $2$ for an answer of roughly $3\times 10^{319}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .