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$ ?
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ Here's a tutorial in MathJax $\endgroup$– Sahiba AroraJun 9, 2017 at 19:19
-
$\begingroup$ So there can be duplicates? $\endgroup$– Mr. XcoderJun 9, 2017 at 19:23
-
$\begingroup$ Yes, duplicates are allowed $\endgroup$– ramana_kJun 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$– luluJun 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$– JMoravitzJun 9, 2017 at 19:41
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
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}$
