|
|
 |
Условие
Для того, чтобы застеклить 15 окон различных размеров и форм, заготовлено 15 стекол в точности по окнам (окна такие, что в каждом окне должно быть одно стекло). Стекольщик, не зная, что стекла подобраны, работает так: он подходит к очередному окну и перебирает неиспользованные стекла до тех пор, пока не найдет достаточно большое (то есть либо в точности подходящее, либо такое, из которого можно вырезать подходящее), если же такого стекла нет, то переходит к следующему окну, и так, пока не обойдет все окна. Составлять стекло из нескольких частей нельзя. Какое максимальное число окон может остаться незастекленными?Решение
Покажем сначала, что если в какой-либо момент осталось не меньше 8 окон (и, соответственно, не меньше 8 стекол), то стекло для какого-нибудь окна из оставшихся можно подобрать. Действительно, разобрано не больше семи стекол, значит хотя бы одно из восьми стекол, предназначавшихся заранее для восьми оставшихся окон, осталось. Его-то и можно вставить в «свое" окно. Поэтому больше семи окон остаться незастекленными не может.Теперь покажем, что семь окон могут остаться незастекленными. Это произойдет, например, в следующем случае. Стекла имеют такие размеры, что для любых двух одно может быть получено из другого вырезанием (заметим, что условие задачи этого не требует). Таким образом, все стекла можно упорядочить от самого маленького до самого большого так, что любое меньшее может быть «вырезано" из большего. Соответствующим образом упорядочиваются и окна. Предположим, стекольщик подходит к окнам в порядке возрастания их размера (от самого маленького к самому большому), а стекла подбирает в порядке убывания размера. При этом ему удастся застеклить 8 самых маленьких окон, восьмое окно получит «свое" стекло. Останутся незастекленными 7 самых больших окон и неиспользованными 7 самых маленьких стекол.
