#math

Запишу решение, чтобы не потерялось, и если кто-то не следит за комментами.

Посмотрим на то, какие бакеты были и какие стали:

было    /------------/------------/------------/------------/------------/
стало   /----/----/----/----/----/----/----/----/----/----/----/----/----/
элементы   *   *      *  **  *     * *  *        *           ** ***    *

Зафиксируем пока число элементов в каждом из изначальных бакетов и посмотрим, какое самое плохое число коллизий может получиться в новом случае.

Утверждается, что если какой-то новый бакет, целиком входящий в старый бакет, непустой, то все числа в нем можно передвинуть до ближайшей границы этого старого бакета и увеличить таким образом число новых коллизий.

Таким образом, в худшем варианте числа лежат только в новых бакетах, пересекающих границу старых (здесь * обозначает потенциальные позиции):

было    -----|------
стало     |-----|
элементы   *****

Для i-го такого нового бакета обозначим за ai количество чисел, лежащих в нем слева от старой границы, а за bi — справа. Тогда сумма квадратов размеров бакетов была C = sum (a[i+1] + bi)^2, а стала C' = sum (ai + bi)^2.

Тогда имеем:

C' = sum (ai + bi)^2

Перепишем сумму через среднее арифметическое:

C' = 4 * sum ((ai + bi) / 2)^2

Применим неравенство о среднем арифметическом и среднем квадратичном:

C' <= 4 * sum (sqrt((ai^2 + bi^2) / 2))^2

Раскроем скобки:

C' <= 2 * sum (ai^2 + bi^2)

Разделим сумму на две, а затем заменим индексы в одной из сумм и сложим обратно:

C' <= 2 * sum (a[i+1]^2 + bi^2) <= 2 * C

Таким образом, доказана нужная оценка с константой 2. Легко проверить, что она достигается.