Arranging books into more piles Some books are arranged into $n$ piles. They're then rearranged into $n+k$ piles, where $k>0$. Show that at least $k+1$ books end up in a smaller pile than before. An induction on $k$ might be appropriate here. The case $k=1$ is that that the books are rearranged into $n+1$ piles, and the statement is at least $2$ books end up in a smaller pile. Suppose the sizes of the piles are $a_1\geq a_2\geq\ldots\geq a_n$ (before) and $b_1\geq b_2\geq\ldots\geq b_{n+1}$ (after).

Let $p_j$ and $p'_j$ be the sizes of the original pile and the new pile, respectively, containing book $j$, $j = 1 \ldots N$, where $N$ is the number of books. Then $n = \sum_{j=1}^N 1/p_j$ while $n+k = \sum_{j=1}^N 1/p'_j$, so $k = \sum_{j=1}^N (1/p'_j - 1/p_j)$. Now if $p'_j \ge p_j$, $1/p'_j - 1/p_j \le 0$, while if $p'_j < p_j$, $1/p'_j - 1/p_j < 1$. Therefore $k$ is less than ...