EvaSchmidt
Ученик
(67)
2 месяца назад
Решение. Сначала опишем стратегию за продавца. Он рассматривает все возможные подмножества кусков, которых всего 4, и отмечает суммарный вес каждого подмножества точкой на отрезке от 0 до 3000 грамм. Так как 0 и 3000 тоже соответствуют некоторым подмножествам (пустому и полному), то отмеченные точки разбивают отрезок [0;3000] на 5 частей. Таким образом, размер одной из частей не превосходит 600 грамм. Если соответствующие подмножества пересекаются, то их пересечение можно убрать, и тогда получится расположить их на двух чашах весов так, чтобы их разница не превышала 600 грамм.
Теперь покажем, как покупателю получить хотя бы 600 грамм. Пусть он порежет головку сыра на куски по 200, 400, 800, 1600 грамм. Несложно проверить, что это разрезание подходит.
Задача. Купившему головку сыра весом 3 кг магазин «Сыр без дыр» предлагает призовую игру. Покупатель режет головку на 4 куска, а продавец выбирает из этих кусков один или несколько и раскладывает их на одну или на обе чаши чашечных весов. Если весы находятся не в равновесии, то продавец за счёт магазина добавляет призовой кусок сыра, уравновешивающий чаши. Продавец старается сделать приз поменьше, а покупатель — побольше. Найдите вес призового куска при наилучших действиях сторон.
Решение. Сначала опишем стратегию за продавца. Он рассматривает все возможные подмножества кусков, которых всего ПРОПУСК, и отмечает суммарный вес каждого подмножества точкой на отрезке от 0 до 3000 грамм. Так как 0 и 3000
тоже соответствуют некоторым подмножествам (пустому и полному), то отмеченные точки разбивают отрезок [0;3000] на ПРОПУСК частей.Таким образом, размер одной из частей не превосходит ПРОПУСК грамм. Если соответствующие подмножества пересекаются, то их пересечение можно убрать, и тогда получится расположить их на двух чашах весов так, чтобы их разница не превышала ПРОПУСК грамм.
Теперь покажем, как покупателю получить хотя бы ПРОПУСК грамм. Пусть он порежет головку сыра на куски по ВЫБРАТЬ ( 100,300,600,2000 или 200,400,800,1600 или 300,600,900,1200 ) грамм. Несложно проверить, что это разрезание подходит.