# Maximizing $\sum\left(\lfloor \frac{n_i}{2} \rfloor+1\right)$ for a partition $\{n_i\}$ of $N$

Let $N$ be a natural number and $\{n_i\}$ be a partition of $N$; by this we mean $1\leq i\leq k$ for some natural number $k$ and $N=n_1+n_2+\cdots+n_k$ where $n_1\geq n_2\geq\ldots\geq n_k\geq1$.

For each such partition $\{n_i\}$ of $N$, consider the sum $$\sum_{i=1}^{\lfloor \frac{k}{2} \rfloor+1}\left(\lfloor \frac{n_i}{2} \rfloor+1\right).$$ (notice that we are summing up to $i=\lfloor \frac{k}{2} \rfloor+1$, not $i=k$)

The problem is to find the maximum value of the above sum, as $\{n_i\}$ varies over all partitions of $N$. If we denote this maximum by $f(N)$, then the first few values of $f$ are $$f(1)=1, f(2)=2, f(3)=3, f(4)=4, \ldots$$ and so on. Is there a way to find $f(N)$ in general? Perhaps (hopefully) an explicit formula for $f(N)$?

I have been struggling with this problem for few hours now, and I don't have a clue on where to start. It looks like one has to use many big, even numbers (when partitioning $N$) to make the sum bigger, but I'm not so sure... Any advice is welcome.

Let $n\ge 3$.

For a partition $p = \{n_1,\dots,n_k\}$ of $n$, define its usefulness as $$u(p) = \sum_{i=1}^{\lfloor \frac{k}{2} \rfloor+1}\left(\left\lfloor \frac{n_i}{2} \right\rfloor+1\right),$$ also call parts $n_i$ with $i\le \left\lfloor \frac{k}{2} \right\rfloor+1$ useful, other parts useless. Consider some operations which do not reduce usefullness:

• If there is a useless part $n_i\ge 2$, split it into singletons. The number of parts increases, so the usefulness will not decrease.

• If there is a useful part $n_i\ge 3$, split it to $(n_i-2)+1+1$. This either reduces the contribution of this part to usefulness by $1$, or this part is replaced by a bigger part, which were useless before. But the number of useful parts increases by $1$, so the total usefulness will not go down.

• If there are at least two useful singletons, merge one of them with a useless singleton. The contribution of the merged part increases by $1$, but one of the useful parts - necessarily a singleton - might become useless, so the usefulness again cannot decrease.

• If there is exactly one useful singleton and $k$ is odd, merge it with a useless singleton, increasing usefulness by one.

After these operations, the partition becomes $2,2,\dots,2,1,1,\dots,1$ with no useless doubletons and either without useful singletons or, in the case of even $k$, with possibly one useful singleton. For given $n$, such a partition $p^*$ is unique and maximizes usefulness, and it is not hard to see that $$f(n) = u(p^*) = \begin{cases} 2k+1, & n = 3k,\\ 2k+2, & n \in\{3k+1,3k+2\}. \end{cases}$$

For $n=1,2$, the last two operations are not available for the partitions $1$ and $1+1$; the formula above is still valid for $n=2$ (since the partition $2$ is of the required form), while $f(1) = 1$.