ПОМОГИТЕ СИРИУС КУРСЫ КОМБИНАТОРИКА 8 КЛАСС

Question

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

Answer 1

Сначала опишем стратегию за продавца. Он рассматривает все возможные подмножества кусков, которых всего 16, и отмечает суммарный вес каждого подмножества точкой на отрезке от 0 до 3000 грамм. Так как 0 и 3000 тоже сответствуют некоторым подмножествам (пустому и полному) , то отмеченные точки разбивают отрезок [0; 3000] на 15 частей. Таким образом, размер одной из частей не превосходит 200 грамм. Если сответствующие подмножества пересекаются, то их пересечение можно убрать, и тогда получится расположить их на двух чашах весов так, чтобы их разница не превышала 200 грамм. Теперь покажем, как покупателю получить хотя бы 200 грамм. Пусть он порежет головку сыра на куски по 200, 400, 800, 1600 грамм. Несложно проверить, что это разрезание подходит.