Proof by induction: Always throw balls from the 2 boxes with most balls, this preserves the a[i]<=s/2 (both a[i] maxes are reduced by 1, s/2 reduced by one, other a[i]'s can't have >s/2 without any of them being the max previously).

Obviously this will only work if you have an even number of balls. Otherwise there will be one ball left at the end.

One method that works is: pick the two boxes with the most balls and remove a ball of each one.

It is easy to see, that when you have still some balls in some boxes, and the inequality holds for all i, then you can always perform this operation because you have at least two non-empty boxes.

The thing left to prove is, that after one operation the inequality still hold. Of course now with s - 2, since we removed two balls: , where a'[i] is the modified array after the operation.

And that's also easy to prove. If there are any boxes with before the operation, then there are at most 2 of them. So you will remove one ball from each of those, and after removing you have .

All other boxes have before the operation, so they are already and this obviously doesn't change by performing the operation.

So to recap: If you are in the situation for all i, then you can perform the operation and end up in the exact same situation. Therefore you can reapeat this as long as you have any balls left. And since you don't have any balls left at the end, all boxes are empty.