This is a MO competition problem, and I have seen some proofs with weird constructions, but I was wondering whether it has some more motivated proof.
Here is my reasoning and the way I might have turned the problem into a more approachable one:
The main idea is to look at how many books there are that are on a shelf with less than or equal to $i$ books. Then if we find $i$ for which difference of that value between the 2 configurations (before and after adding new shelves) is maximized, we know that some books from shelves with more than $i$ books have to be set to those with less or equal, and the amount of books is equal to that difference. Array $d$ is the difference in number of books that are on shelves with exactly $i$ books between 2 configurations.
I apologize for bad wording, it's hard for me to concisely phrase my reasoning for this problem, and that's why I initially only posted the derived problem without the background.
Anyways, here's that problem:
$d_i$ is the difference in number of books that are on shelves with exactly $i$ books between 2 configurations
let $(d_1, d_2, d_3,...,d_m)$ be an array of integers s.t.
$d_1+d_2+d_3+...+d_m=k, k>0$
and
$d_1+2d_2+3d_3+...+md_m=0$
what is the lower bound for a maximum element of a set
$\{d_1, \; d_1+2d_2, \; d_1+2d_2+3d_3,\;...,\;d_1+2d_2+3d_3+...+md_m \}?$