Имеется несколько дынь, вес каждой дыни не более 5 кг. Оказалось, что как бы мы ни разложили эти дыни на две кучки, вес хотя бы одной из кучек тоже будет не больше 5 кг. Чему равен наибольший возможный вес всех дынь? задан 16 Июн '19 23:19 Казвертеночка
показано 5 из 7
показать еще 2
|
15 кг. Пример очевиден (3 гири по 5). Доказательство оценки: Начнем набирать кучку с самых маленьких дынь, все увеличивая их размер до тех пор, пока эта кучка все еще весит не больше 5 кг. В какой-то момент мы не сможем этого сделать. Что это значит? Что если положить сюда же СЛЕДУЮЩУЮ гирю, то все большие ее должны образовать вторую кучку,меньшую 5 кг. Но тогда все вместе весит не больше, чем 5+5+вес этой следующей гири. То есть не более 15.
@knop: а я вчера прочитал условие, и безуспешно пытался доказывать, что максимальное значение равно 12,5 -- когда все дыни по 2 с половиной :)
@knop, @falcao, большое спасибо!
@falcao, ну такая мысль у меня тоже была.
@knop: а у меня была мысль о весах дынь, стремящихся к нулю, но я к этому моменту уже "уверовал" в оптимальность примера с 12,5 кг. А также "беспокоило" то, что я не мог с нескольких попыток доказать факт, казавшийся каким-то совсем простым :)
@knop, вовсе не обязательно набирать кучку именно с самых маленьких дынь. Можно набирать в любом порядке. Первая попавшаяся дыня будет в любом случае не тяжелее 5 кг. Далее, если суммарная масса всех дынь не больше 5 кг, то она и не больше 15 кг. Если же суммарная масса всех гирь больше 15 кг, то... дальше уже согласно Вашему решению.
@Казвертеночка: в доказательствах такого типа часто делают процесс однозначным. Это не обязательно, но для кого-то более удобен "детерминированный" способ. Конечно, можно ограничение и не вводить, но тут различия уже чисто "вкусовые".