Maximizing a sum of products restricted to another sum of products Let $n\in\mathbb{N}^{\geq 3}$ be a constant and $S=\{e, h_2,\ldots,h_n\}$ a set of variables where each $h_i\in\mathbb{N}^{\geq0}$ and $e\in\{0, 1\}$. The problem is: $$
\begin{split}
\min\quad& m=\sum_{i=2}^n ih_i\\
\text{s.t.}\quad&
n=e+\sum_{i=2}^n (i+1)h_i
\end{split}
$$
Edited. Solution: I'd like to know if there's any, simpler, way to reach to the same conclusion; specifically, which already known-thereoms do exists that I can use to shorten the proof, because I have expend to much time thinking how to remove, in an elegant way, the remainders as variables. After all, this is very similar to the Knapsack problem but not quite the same because of the equality restriction, so there must be plenty of well-known results out there, but I haven't been able to find a suitable one for me.
NOTE: Writting $n=\underline{a}q+r$ means that $q$ and $r$ are the quotient and remainder of $n/a$ respectively.
Given a solution $S=\{e, h_2, \ldots, h_n\}$, let's call $H=\sum_{i=2}^nh_i$. Then: $$
n=e+\sum_{i=2}^n(i+1)h_i=e+H+m\iff m=n-(e+H)
$$
Which means minimizing $m$ implies maximizing $e+H$. Knowing its $H$ and $e$, any solution $S$ can be simplified to $S'=\{e', h'_a, h'_{a+1}\}$ with any other $h'_x=0$ (so they are omitted) by expressing $n$ as $$
n=\underline{H}(a+1)+r = h'_{a+1}(a+2)+h'_a(a+1)+e'
$$
where $H=h'_{a+1}+h'_a$, $e'=e$, and $r=h'_{a+1}+e'$. Notice that $n\geq 3\implies H\geq 1\implies n\geq 3H$; $a+1\geq 3$, and so $a\geq 2$ is a valid variable index and $S'$ a valid solution. This solution $S'$ is equivalent to $S$ because $H$ and $e$, and consequently $m$ and $n$, haven't changed.
That means the set of simplified solutions is complete for the problem, which can be reestated as, given $n\in\mathbb{N}^{\geq3}$, $$
\begin{split}
\max\quad& H+e\\
\text{s.t.}\quad&
n=\underline{H}(a+1)+r\\
&e\leq \min(1, r)\\
&a\geq 2
\end{split}\implies\begin{split}
\max\quad & H+\min(1,r)\\
\text{s.t.}\quad & n=\underline{H}(a+1)+r\\
& a\geq 2
\end{split}\implies\begin{split}
\max\quad & H\\
\text{s.t.}\quad & n=\underline{H}(a+1)+r\\
& a\geq 2
\end{split}
$$ where $H$ is our only variable now. The last step is explained because, since $\min(1, r)\in\{0, 1\}$, decreasing $H$ never increases $H+\min(1, r)$, and thus increasing $H$ doesn't affect the optimality of $H+\min(1, r)$. In other words, we only need to optimize $H$.
Now consider that an optimal $H$ gives an $r$ that is also remainder of $n/(a+1)$. Otherwise, $r=k\underline{(a+1)}+q$ and thus $H$ can grow by $k\geq 1$ units with $a$ fixed. That means the set of solutions where $r\geq a+1$ contains no optimal solution. Reestating again: $$
\begin{split}
\max\quad & H\\
\text{s.t.}\quad & n=H\underline{(a+1)}+r\\
& a\geq 2
\end{split}\implies\begin{split}
\max\quad & \left\lfloor\frac{n}{a+1}\right\rfloor\\
\text{s.t.}\quad & a\geq 2
\end{split}\implies a=2
$$
The optimal solution is then (where $r$ is the remainder of $n/3$), $$
\begin{split}
H\quad&= \lfloor n/3\rfloor = (n-r)/3\\
e\quad&= \min(1, r)\\
h_3\quad&= r-e\\
h_2\quad& = H-h_3 = \lfloor n/3\rfloor - (r-e)\\
m\quad& = 2h_2+3h_3 = 2H+r-e
\end{split}
$$
where $m$ can be further simplified by $$
m=2\frac{n-r}{3}+r-e=\frac{2n+r-3e}{3}=\left\lfloor
\frac{2n+(r-3e)-(r-3e)}{3}\right\rfloor$$$$
\iff \boxed{m= \left\lfloor\frac{2n}{3}\right\rfloor}
$$
The last step is explained because, since $2n+r-3e$ divides $3$, adding any amount between $0$ and $2$ won't change its value when inside of the floor function. Since $r-3e\in\{0, -2, -1\}$ for $r=0,1,2$ respectively, adding $-(r-3e)$ is a valid amount.
 A: Let’s handle the case where there’s no $e$ and the variables don’t have to be integers first. In that case, since all the integers are unbounded above, there’d be an optimal solution where only one variable is nonzero. Given a solution where two variables are nonzero, increasing one of those variables slightly and decreasing the other accordingly will only either increase $H$, or decrease $H$, or keep $H$ constant. And since everything’s linear, you can move in whichever direction is best until one of those variables is 0, without decreasing $H$. So in the continuous case, you just have to choose which $h_i$ is the best. Clearly, it’s $h_2$, so you’d take $h_2=n/3$.
Then you just have to handle the integer restriction, and put $e$ back in. Clearly, if $n=3k+1$, you take $e=1$ and keep your solution from the continuous case. If $n=3k$, you can take $h_2=n/3$ and $e=0$, and you can check that no other integer solution is better. Similarly, if $n=3k+2$, you can take $h_3=1,e=1,h_2=(n-2)/3$, and show that no other integer solution is better.
