Задания
Версия для печати и копирования в MS Word
Тип 19 № 695399
i

В циф­ро­вом хра­ни­ли­ще дан­ные раз­би­ты на не­сколь­ко оди­на­ко­вых по раз­ме­ру дис­ков, но сей­час на них за­ня­то раз­ное ко­ли­че­ство те­ра­байт. Си­сте­ма может за одну опе­ра­цию пе­ре­ме­стить любое ко­ли­че­ство дан­ных с од­но­го диска на дру­гой.

а)  Есть 4 диска, на ко­то­рых за­ня­то 70, 78, 76, 72 ТБ. За какое наи­мень­шее число опе­ра­ций пе­ре­ме­ще­ния дан­ных можно урав­нять объём за­ня­то­го про­стран­ства на всех дис­ках?

б)  Пред­по­ло­жим, дис­ков 10. Все­гда ли можно урав­нять за­ня­тое про­стран­ство на всех дис­ках не более чем за 6 опе­ра­ций?

в)  За какое наи­мень­шее ко­ли­че­ство опе­ра­ций можно за­ве­до­мо урав­нять за­ня­тое про­стран­ство на 2026 дис­ках?

Спрятать решение

Ре­ше­ние.

а)  За одну опе­ра­цию сде­лать это не­воз­мож­но, по­то­му что у двух дис­ков не из­ме­нит­ся объем за­ня­то­го про­стран­ства, а у всех дис­ков он раз­лич­ный. По­ка­жем, как можно урав­нять объ­е­мы дис­ков за две опе­ра­ции. Пе­ре­не­сем сна­ча­ла 4 ТБ со вто­ро­го диска на пер­вый, а затем 2 ТБ с тре­тье­го на чет­вер­тый. В таком слу­чае на каж­дом из дис­ков будет за­ня­то по 74 ТБ.

б)  Пусть на одном диске за­ня­то 10 ТБ, а осталь­ные де­вять пусты. Если каж­дой из опе­ра­ций за­пол­нять не­ко­то­рым объ­е­мом пу­стой диск, то через 6 опе­ра­ций не более 7 дис­ков ока­жут­ся не­пу­сты­ми. Для урав­ни­ва­ния про­стран­ства на 10 дис­ках каж­дый из них дол­жен быть занят.

в)  До­ка­жем, что хва­тит 2025 опе­ра­ций. Пусть сум­мар­ный объем за­ня­то­го про­стран­ства равен  2026x ТБ. Для каж­дой опе­ра­ции будем вы­би­рать диск, на ко­то­ром за­ня­то боль­ше x ТБ, и диск, на ко­то­ром за­ня­то мень­ше x ТБ, и пе­ре­ме­щать дан­ные с более за­ня­то­го на менее за­ня­тый до тех пор, пока на одном из дис­ков объем не ста­нет равен x ТБ. Таким об­ра­зом, после каж­дой опе­ра­ции ста­но­вит­ся ми­ни­мум на один диск с объ­е­мом, рав­ным x ТБ, боль­ше. Через 2025 таких опе­ра­ций на 2025 дис­ках будет со­от­вет­ствен­но x ТБ дан­ных, а на по­след­нем диске ока­жет­ся  2026x минус 2025x = x ТБ, по­это­му все урав­ня­ет­ся.

От­ме­тим, что до мо­мен­та урав­ни­ва­ния объ­е­мов всех дис­ков обя­за­тель­но най­дет­ся диск, на ко­то­ром за­ня­то боль­ше x ТБ, и диск, на ко­то­ром за­ня­то мень­ше x ТБ. Если, ска­жем, диска, на ко­то­ром за­ня­то боль­ше x ТБ, не будет, то сум­мар­ный объем ин­фор­ма­ции будет мень­ше  2026x ТБ, а это про­ти­во­ре­чит усло­вию.

 

Ответ: а)  да; б)  нет; в)  2025.

Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Обос­но­ван­но по­лу­че­ны вер­ные от­ве­ты в пунк­тах а), б) и в).4
Обос­но­ван­но по­лу­чен вер­ный ответ в пунк­те в) и обос­но­ван­но по­лу­чен вер­ный ответ в пунк­те а) или б).3
Обос­но­ван­но по­лу­че­ны вер­ные от­ве­ты в пунк­тах а) и б)

ИЛИ

обос­но­ван­но по­лу­чен вер­ный ответ в пунк­те в)

2
Обос­но­ван­но по­лу­чен вер­ный ответ в пунк­те а) или б).1
Ре­ше­ние не со­от­вет­ству­ет ни од­но­му из кри­те­ри­ев, пе­ре­чис­лен­ных выше.0
Мак­си­маль­ный балл4

Аналоги к заданию № 514432: 695399 Все

Источник: А. Ларин. Тре­ни­ро­воч­ный ва­ри­ант № 527
Классификатор алгебры: Сю­жет­ные за­да­чи: кино, театр, мотки верёвки