Тип 19 № 695399 
Числа и их свойства. Сюжетные задачи: кино, театр, мотки верёвки
i
В цифровом хранилище данные разбиты на несколько одинаковых по размеру дисков, но сейчас на них занято разное количество терабайт. Система может за одну операцию переместить любое количество данных с одного диска на другой.
а) Есть 4 диска, на которых занято 70, 78, 76, 72 ТБ. За какое наименьшее число операций перемещения данных можно уравнять объём занятого пространства на всех дисках?
б) Предположим, дисков 10. Всегда ли можно уравнять занятое пространство на всех дисках не более чем за 6 операций?
в) За какое наименьшее количество операций можно заведомо уравнять занятое пространство на 2026 дисках?
Решение. а) За одну операцию сделать это невозможно, потому что у двух дисков не изменится объем занятого пространства, а у всех дисков он различный. Покажем, как можно уравнять объемы дисков за две операции. Перенесем сначала 4 ТБ со второго диска на первый, а затем 2 ТБ с третьего на четвертый. В таком случае на каждом из дисков будет занято по 74 ТБ.
б) Пусть на одном диске занято 10 ТБ, а остальные девять пусты. Если каждой из операций заполнять некоторым объемом пустой диск, то через 6 операций не более 7 дисков окажутся непустыми. Для уравнивания пространства на 10 дисках каждый из них должен быть занят.
в) Докажем, что хватит 2025 операций. Пусть суммарный объем занятого пространства равен 
Для каждой операции будем выбирать диск, на котором занято больше x ТБ, и диск, на котором занято меньше x ТБ, и перемещать данные с более занятого на менее занятый до тех пор, пока на одном из дисков объем не станет равен x ТБ. Таким образом, после каждой операции становится минимум на один диск с объемом, равным x ТБ, больше. Через 2025 таких операций на 2025 дисках будет соответственно x ТБ данных, а на последнем диске окажется 
поэтому все уравняется.
Отметим, что до момента уравнивания объемов всех дисков обязательно найдется диск, на котором занято больше x ТБ, и диск, на котором занято меньше x ТБ. Если, скажем, диска, на котором занято больше x ТБ, не будет, то суммарный объем информации будет меньше 
а это противоречит условию.
Ответ: а) да; б) нет; в) 2025.
Критерии проверки:| Критерии оценивания выполнения задания | Баллы |
|---|
| Обоснованно получены верные ответы в пунктах а), б) и в). | 4 |
| Обоснованно получен верный ответ в пункте в) и обоснованно получен верный ответ в пункте а) или б). | 3 |
| Обоснованно получены верные ответы в пунктах а) и б) ИЛИ обоснованно получен верный ответ в пункте в) | 2 |
| Обоснованно получен верный ответ в пункте а) или б). | 1 |
| Решение не соответствует ни одному из критериев, перечисленных выше. | 0 |
| Максимальный балл | 4 |
Ответ: а) да; б) нет; в) 2025.
695399
а) да; б) нет; в) 2025.
PDF-версии: