6
$\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$
  • 1
    $\begingroup$ Here's a tutorial in MathJax $\endgroup$ – Sahiba Arora Jun 9 '17 at 19:19
  • $\begingroup$ So there can be duplicates? $\endgroup$ – Mr. Xcoder Jun 9 '17 at 19:23
  • $\begingroup$ Yes, duplicates are allowed $\endgroup$ – brad_tx Jun 9 '17 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 Jun 9 '17 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 Jun 9 '17 at 19:41
5
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.