Partition n elements to k group to maximize this function We have $n$ elements and two integers $k,m$ such that $n \gg k, n \gg m$ and we need to partition the n elements to k groups in a way that would maximize the following function:
sum = 0
For each group S in the partition:
    If |S| <= m:
        sum += |S|
    Else:
        sum += |S|/(|S|-m)
return sum

What is the maximum value this function can get?
It's easy to see that if $m=0$ this maximum value would be $k$ because if there would be at least 1 element in each group the sum would be k. If $m>0$ we can bound this function with $(m+1)k$ (each group adds at most $m+1$ when $|S| = m+1$) but I didn't thought of any way to calculate the maximum value in the case $m > 0$, the $(m+1)k$ is obviously not a tight bound bound because if $n \gg m, n\gg k$ it's impossible all the groups would have only $m+1$ elements.
My intuition tells me that the optimal solution would be to put $m+1$ elements in each group and the rest in the last group, but I'm not sure how to prove it.
 A: Your intuition is correct! To prove it, I will use the properties of convex functions.
Let us define $f(x):=\min\left(x,1+\frac{x}{x-m}\right)$ on $(0,\infty)$. Note that the two functions coincide at $x=m+1$. In addition, define $A:=\{x\in\Bbb R_+^k\mid x_1+\cdots+x_k=n\}$, where $\Bbb R_+$ is the set positive real numbers. For $x\in\Bbb R_+^k$, define $F(x)=\sum_{i=1}^kf(x_i)$. By some simple reasoning, we find that you are looking for 
$$\max_{x\in A\cap\Bbb N^k}F(x),$$
where $\Bbb N$ is the set of positive integers. Instead of talking about partitions of $n$, we will talk about elements of $A$.
Case 1. Suppose $k(m+1)\geq n$. Note that, by definition of $F$ and $f$,
$$\forall x\in\Bbb R_+^k,\quad F(x)\leq\sum_{i=1}^kx_i=n.$$
Take any $x\in A$ where $\forall i,\;|x_i|\leq m+1$. In fact, we can take $x\in A\cap\Bbb N^k$. We find that $F(x)=n$, which is the maximal possible value of $F$, so the maximal value of $F$ on $A\cap\Bbb N^k$ is indeed $n$.
Case 2. Now suppose $k(m+1)<n$ (presumably, if $k,m\ll n$, then this is the more likely case). Let $x\in A$. If there exists $i$ such that $x_i<m+1$, then there exists $x_j>m+1$, and
$$F(\ldots,x_i,\ldots,x_j,\ldots)<F(\ldots,x_i+1,\ldots,x_j-1,\ldots),$$
where we do not change any of the other values. This is because $f(x_i+1)=x_i+1>x_i=f(x_i)$ and $f(x_j-1)=\frac{x_j-1}{x_j-1-m}>\frac{x_j}{x_j-m}=f(x_j)$. Therefore, repeating this process as long as one coordinate of $x$ is smaller than $m+1$, we conclude that it suffices to maximize $F$ on
$$B:=A\cap[m+1,\infty)^k=\left\{x\in\Bbb R_+^k\left|\begin{array}{l}
x_1+\cdots+x_k=n\\
\forall i,\; x_i\geq m+1
\end{array}\right.\right\}.$$
But the function $F$ restricted to $B$ is simply $\sum_{i=1}^k\frac{x_k}{x_k-m}$, which is a convex function, and $B$ is a convex set. Therefore the maximal value of $F$ on $B$ is reached on one of the extremal points of $B$. By symmetry, it is reached for
$$x_0=(m+1,\ldots,m+1,n-(k-1)(m+1)),$$
which has integer coordinates. We conclude that the maximal value of $F$ on $A\cap\Bbb N^k$ is
$$F(x_0)=(k-1)(m+1)+\frac{n-(k-1)(m+1)}{n-(k-1)(m+1)-m},$$
which you can simplify as you wish.
