Let $n\geq 2$ be an integer. For each $k$-tuple of positive integers $a_1, a_2, \ldots, a_k$ such that $a_1+a_2+\cdots +a_k=n$, consider the sums $S_i=1+2+\ldots +a_i$ for $1\leq i\leq k$. Determine, in terms of $n$, the maximum possible value of the product $S_1S_2\cdots S_k$. Proposed by Misael Pelayo
Problem
Source: Mexico National Olympiad 2018 Problem 4
Tags: algebra, Inequality, maximum value, positive integers
plagueis
07.11.2018 05:41
Prove that if $S_1S_2\cdots S_n$ is maximized, then each one of $a_1, a_2, \ldots, a_n$ is less than or equal to $4$.
GovernmentCheeseAhoy
07.11.2018 08:04
plagueis wrote:
Prove that if $S_1S_2\cdots S_n$ is maximized, then each one of $a_1, a_2, \ldots, a_n$ is less than or equal to $3$.
I think it should be less than or equal to 4. For example, the maximum product for n=7 is (1+2+3)(1+2+3+4)=60.
MiltonMath12
07.11.2018 09:54
Note that $S_{i}=\frac{a_{i}(a_{i}+1)}{2}$ therefore $max(\frac{\prod_{i=1}^ka_{i}(a_{i}+1)}{2^k})=M$ then we look for the maximum of the product of all the $a_{i}$ since if this is maximum it will also be the maximum of $a_{i}+1$ Using the hint Suppose exist any $a_{i}$ such that $a_{i}\geq4$ but $3(a_{i}-3) \geq a_{1}$ for all $a_{i}\geq\frac{9}{2}$, which is a contradiction. Therefore $a_{i}\leq4$ but if $a_{i}=4$ we could change it for two 2's therefore $a_{i}\leq3$ therefore all $a_ {i}$ are $2$ or $3$. if de maximum is when $a_{i}=3$ So $M=3^k2^k$ or $M=3^k$ and the maximum is when for all $i$ $a_i=3$ And $M=6^{\frac{n}{3}}$ the last argument does not convince me but I'm waiting for your opinion
GovernmentCheeseAhoy
08.11.2018 02:12
MiltonMath12 wrote: Note that $S_{i}=\frac{a_{i}(a_{i}+1)}{2}$ therefore $max(\frac{\prod_{i=1}^ka_{i}(a_{i}+1)}{2^k})=M$ then we look for the maximum of the product of all the $a_{i}$ since if this is maximum it will also be the maximum of $a_{i}+1$ Using the hint Suppose exist any $a_{i}$ such that $a_{i}\geq4$ but $3(a_{i}-3) \geq a_{1}$ for all $a_{i}\geq\frac{9}{2}$, which is a contradiction. Therefore $a_{i}\leq4$ but if $a_{i}=4$ we could change it for two 2's therefore $a_{i}\leq3$ therefore all $a_ {i}$ are $2$ or $3$. if de maximum is when $a_{i}=3$ So $M=3^k2^k$ or $M=3^k$ and the maximum is when for all $i$ $a_i=3$ And $M=6^{\frac{n}{3}}$ the last argument does not convince me but I'm waiting for your opinion Unfortunately most of this is incorrect. You said "then we look for the maximum of the product of all the $a_{i}$ since if this is maximum it will also be the maximum of $a_{i}+1$", but this is not always true. For example, for n=7, a_1=3, a_2=4 give us the maximum product of the S_i's (60) however this doesn't give us the maximum value of (a_1+1)...(a_k+1) (4*3*3=36>4*5=20). The idea of using small a_i's without that assumption does work but they have to be <=4 (check the corrected hint).
MiltonMath12
08.11.2018 02:54
GovernmentCheeseAhoy wrote: MiltonMath12 wrote: Note that $S_{i}=\frac{a_{i}(a_{i}+1)}{2}$ therefore $max(\frac{\prod_{i=1}^ka_{i}(a_{i}+1)}{2^k})=M$ then we look for the maximum of the product of all the $a_{i}$ since if this is maximum it will also be the maximum of $a_{i}+1$ Using the hint Suppose exist any $a_{i}$ such that $a_{i}\geq4$ but $3(a_{i}-3) \geq a_{1}$ for all $a_{i}\geq\frac{9}{2}$, which is a contradiction. Therefore $a_{i}\leq4$ but if $a_{i}=4$ we could change it for two 2's therefore $a_{i}\leq3$ therefore all $a_ {i}$ are $2$ or $3$. if de maximum is when $a_{i}=3$ So $M=3^k2^k$ or $M=3^k$ and the maximum is when for all $i$ $a_i=3$ And $M=6^{\frac{n}{3}}$ the last argument does not convince me but I'm waiting for your opinion Unfortunately most of this is incorrect. You said "then we look for the maximum of the product of all the $a_{i}$ since if this is maximum it will also be the maximum of $a_{i}+1$", but this is not always true. For example, for n=7, a_1=3, a_2=4 give us the maximum product of the S_i's (60) however this doesn't give us the maximum value of (a_1+1)...(a_k+1) (4*3*3=36>4*5=20). The idea of using small a_i's without that assumption does work but they have to be <=4 (check the corrected hint). Ammm if I understand your counterexample well are you using 4 * 3 * 3 but 4 + 3 + 3 is not 7, or am I misunderstanding it? And in no configuration of 4 * 3 * 3 the sum is 7
GovernmentCheeseAhoy
08.11.2018 03:38
@above By 4*3*3, i meant a_1=3, a_2=2, a_3=2.
MiltonMath12
08.11.2018 03:51
But your example is false given that by hint $a_ {i}\leq3$
GovernmentCheeseAhoy
08.11.2018 03:58
The hint was corrected. It's <=4
MiltonMath12
08.11.2018 04:02
But if some $a_ {i}$ is $4$ then we could exchange it for two $2's$
GovernmentCheeseAhoy
08.11.2018 04:11
Not really. As I said, that's assuming that maximizing the product of the a_i's also gives you the maximum value of the product of the S_i's, which is not always true. 60=(1+2+3)(1+2+3+4)>(1+2+3)(1+2)(1+2)=54.
plagueis
08.11.2018 05:22
Let $a_1, a_2, \ldots, a_k$ be a tuple which maximizes the product $S_1S_2\cdots S_k$.
Claim 1. There does not exist $a_i\geq 5$.
Proof. Let us suppose that there exists $a_i\geq 5$. Let us note that if in place of $a_i$ we use $a_j=a_i-2$ and $a_l=2$ then $S_i<S_jS_l$. To prove this we see that $s_i=a_i (a_i+1)/2$ and $s_j\cdot s_l=3(a_i-2)(a_i-1)/2$, then $s_i<s_j\cdot s_l$ holds if and only if $3(a_i-2)(a_i-1)>a_i (a_i+1)$ which in turn holds if and only if $2a_i^2+6>10a_i$ but with $a_i\geq 5$ we even have $2a_i^2>10a_i$. With this, we find a tuple with greater product of the $S_i$, contradicting the supposition that some $a_i$ is greater than or equal to $5$.
Claim 2. There does not exist $a_i=1$.
Proof. If some $a_i$ is equal to $1$ then the product $s_1\ldots s_k$ would be greater removing that term, taking other random $a_j$ and adding $1$ (this is possible since we can easily check that a configuraction with maximum product should have more that one $a_i$ since $n>1$), a contradiction to the maximality of the product. Therefore, we cannot have $a_i=1$.
So each $a_i$ is equal to $2$, $3$, $4$.
Claim 3. There do not exist two $a_i, a_j$ equal to $2$.
Proof. Let us note that if $a_i, a_j=2$ then we can remove $a_j$ and set $a_i=4$, which would change the product $3\cdot 3\cdot s_1\cdots s_k$ to $10\cdot s_1\cdots s_k$. This is again a contradiction to the maximality of our product. Thus we have at most one $2$.
Claim 4. We have at most one $a_i$ with $a_i=4$.
Proof. Suppose the contrary, we have $a_i, a_j=4$. Let us replace these terms by two terms $3$ and one $2$. Thus the product is greater in a proportion $108/100$ . Contradiction
Claim 5. There do not exist $i, j$ with $a_i=2$ and $a_j=4$.
Proof. Let us replace these two terms by two terms $3$. This increases the product in a proportion of $36/30$. Contradiction.
From the claims, we obtain that the tuple with the maximum product is:
a) $3, 3, \cdots, 3$ if $n=3m$
b) $3, 3, \cdots, 3, 4$ if $n=3m+1$
c) $3, 3, \cdots, 3, 2$ if $n=3m+2$
with products $6^m, 10\cdot 6^{m-1}$ and $3\cdot 6^m$, respectively.
IWantToBeNutellaSomeday
02.04.2020 07:38
I misunderstood the problem. I thought that $N$ and $K$ were fixed. But reading this now both the problem and the solution are clear. My question is, given $n$ and $k$ then the solution is $$ \left( \frac{n-m}{k} \right)^{k-m} \left( \frac{n+k-m}{k} \right)^{m} $$ ? Where $ m = n $ mod $k$. My idea was trying to make $ |a_ i - a_j| \leq 1 $. Is this correct? And if so, how to prove it?
plagueis
18.06.2020 07:08
IWantToBeNutellaSomeday wrote: I misunderstood the problem. I thought that $N$ and $K$ were fixed. But reading this now both the problem and the solution are clear. My question is, given $n$ and $k$ then the solution is $$ \left( \frac{n-m}{k} \right)^{k-m} \left( \frac{n+k-m}{k} \right)^{m} $$ ? Where $ m = n $ mod $k$. My idea was trying to make $ |a_ i - a_j| \leq 1 $. Is this correct? And if so, how to prove it? Hi! Maybe a bit late but... Only $n$ is fixed, which means that your answer should not depend on $k$