В цифровом хранилище данные разбиты на несколько одинаковых по размеру дисков, но сейчас на них занято разное количество терабайт. Система может за одну операцию переместить любое количество данных с одного диска на другой.
а) Есть 4 диска, на которых
б) Предположим, дисков 10. Всегда ли можно уравнять занятое пространство на всех дисках не более чем за 6 операций?
в) За какое наименьшее количество операций можно заведомо уравнять занятое пространство на 2026 дисках?
а) За одну операцию сделать это невозможно, потому что у двух дисков не изменится объем занятого пространства, а у всех дисков он различный. Покажем, как можно уравнять объемы дисков за две операции. Перенесем сначала 4 ТБ со второго диска на первый, а затем 2 ТБ с третьего на четвертый. В таком случае на каждом из дисков будет занято по 74 ТБ.
б) Пусть на одном диске занято 10 ТБ, а остальные девять пусты. Если каждой из операций заполнять некоторым объемом пустой диск, то через 6 операций не более 7 дисков окажутся непустыми. Для уравнивания пространства на 10 дисках каждый из них должен быть занят.
в) Докажем, что хватит 2025 операций. Пусть суммарный объем занятого пространства
Отметим, что до момента уравнивания объемов всех дисков обязательно найдется диск, на котором занято больше x ТБ, и диск, на котором занято меньше x ТБ. Если, скажем, диска, на котором занято больше x ТБ, не будет, то суммарный объем информации будет
Ответ: а) да; б) нет; в) 2025.

