2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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