A simple quadratic integer optimization problem

Question

Consider the following optimization problem in positive integers $n_1, n_2, n_3$.

$$\begin{array}{ll} \text{maximize} & n_1(n_2+n_3)\\ \text{subject to} & n_1+n_2+n_3 = N\end{array}$$

If $n_1, n_2, n_3$ were reals, the solution would be $n_1 = \frac N2$ and $n_2 = n_3$. However, in my problem, $n_1, n_2, n_3$ are positive integers. Please help me solve this quadratic integer optimization problem.

Answer 1

It is readily apparent that:

1. if $N \le 2$, the problem is infeasible

2. if $N = 3$, the optimal solution is [1,1,1]

3. If $N = 4$, the optimal solution is [2,1,1]

4. If $N \ge 5$ and odd, then the optimal solutions are

   a) $n_1 = \lfloor N/2 \rfloor$, $n_2$ and $n_3$ being any combination of positive integers summing to $N - n_1$

   b) $n_1 = \lceil N/2 \rceil$, $n_2$ and $n_3$ being any combination of positive integers summing to $N - n_1$

5. If $N \ge 6$ and even, then the optimal solutions are $n_1 = N/2$, $n_2$ and $n_3$ being any combination of positive integers summing to $N/2$