Question

9. Для того, чтобы застеклить 15 окон различных размеров и форм, заготовлено 15 стекол в точностипо окнам (в каждом окне должно быть одно стекло). Стекольщик, не зная, что стекла подобраны,работает так: он подходит к очередному окну и перебирает неиспользованные стекла до тех пор,пока не найдет достаточно большое (т.е. либо в точности подходящее, либо такое, из которогоможно вырезать подходящее), если же такого стекла нет, то переходит к следующему окну, и так,Пока не обойдет все окна. Составлять стекло из нескольких частей нельзя. Какое максимальноеЧИСло окон может остаться незастекленными?​

Answer 1

Ответ:

Пошаговое объяснение:

Решение

Покажем сначала, что если в какой-либо момент осталось не меньше 8 окон (и, соответственно, не меньше 8 стекол), то стекло для какого-нибудь окна из оставшихся можно подобрать. Действительно, разобрано не больше семи стекол, значит хотя бы одно из восьми стекол, предназначавшихся заранее для восьми оставшихся окон, осталось. Его-то и можно вставить в «свое" окно. Поэтому больше семи окон остаться незастекленными не может.

Теперь покажем, что семь окон могут остаться незастекленными. Это произойдет, например, в следующем случае. Стекла имеют такие размеры, что для любых двух одно может быть получено из другого вырезанием (заметим, что условие задачи этого не требует). Таким образом, все стекла можно упорядочить от самого маленького до самого большого так, что любое меньшее может быть «вырезано" из большего. Соответствующим образом упорядочиваются и окна. Предположим, стекольщик подходит к окнам в порядке возрастания их размера (от самого маленького к самому большому), а стекла подбирает в порядке убывания размера. При этом ему удастся застеклить 8 самых маленьких окон, восьмое окно получит «свое" стекло. Останутся незастекленными 7 самых больших окон и неиспользованными 7 самых маленьких стекол.

Answer 2

Давайте рассмотрим данный вопрос. У нас есть 15 окон различных размеров и форм, а также 15 стекол. Стекла можно сопоставить окнам так, чтобы каждое окно получило подходящее стекло.

Стекольщик начинает с первого окна и ищет подходящее стекло. Если он находит подходящее стекло для первого окна, то оно стекается. Затем он переходит ко второму окну и так далее, пока не обработает все 15 окон.

Таким образом, при оптимальной организации процесса, все 15 окон должны быть застеклены. Ни одно окно не останется незастекленным, так как для каждого окна найдется подходящее стекло (или такое, из которого можно вырезать подходящее).

Исходя из условий задачи, ни одно окно не должно остаться незастекленным.