Задача 7
Задача 7. Купившему головку сыра весом 3 кг магазин «Сыр без дыр» предлагает призовую игру. Покупатель режет головку на 4 куска, а продавец выбирает из этих кусков один или несколько и раскладывает их на одну или на обе чаши чашечных весов. Если весы находятся не в равновесии, то продавец за счёт магазина добавляет призовой кусок сыра, уравновешивающий чаши. Продавец старается сделать приз поменьше, а покупатель — побольше. Найдите вес призового куска при наилучших действиях сторон.
Решение. Сначала рассмотрим стратегию продавца. Он рассматривает все возможные подмножества кусков, которых всего 2⁴ = 16, и отмечает суммарный вес каждого подмножества точкой на отрезке от 0 до 3000 г. Так как 0 и 3000 тоже соответствуют некоторым подмножествам (пустому и полному), то отмеченные точки разбивают отрезок [0; 3000] на 15 частей. Таким образом, размер одной из частей не превосходит 200 г. Если соответствующие подмножества пересекаются, то их пересечение можно убрать, и тогда получится расположить их на двух чашах весов так, чтобы их разница не превышала 200 г.
Покажем, как покупателю получить хотя бы 200 грамм. Для этого он может порезать головку сыра на куски по 200, 400, 800 и 1600 г. Несложно проверить, что это разрезание подходит.
Ответ: 200 г.