ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111639
Темы:    [ Графики и ГМТ на координатной плоскости ]
[ Перебор случаев ]
[ Разбиения на пары и группы; биекции ]
[ Числовые таблицы и их свойства ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

В магазине продают DVD-диски – по одному и упаковками двух видов (упаковки разных видов различаются по количеству и стоимости). Вася подсчитал, сколько требуется денег, чтобы купить N дисков (если выгоднее всего купить больше дисков, чем нужно – Вася так и делает):

Сколько дисков было в упаковках и по какой цене упаковки продавались?
Какое количество денег необходимо Васе, чтобы купить не менее 29 дисков?


Решение 1

  Если наиболее выгодная покупка состоит из нескольких блоков (дисков по отдельности и упаковок), то диски, содержащиеся в любом блоке или любом наборе этих блоков, были куплены способом, который нельзя "улучшить" (сделать более выгодным) – иначе, "улучшая" способ оплаты части дисков, мы бы смогли сделать более выгодной и всю покупку целиком.
  Из этого следует, что если мы использовали для покупок какую-то упаковку, то для покупки такого количества дисков, какое содержится в этой упаковке, по минимальной цене можно покупать одну эту упаковку.
  Из таблицы видно, что диски в количестве 1, 2, 3, 4, 5 покупались по отдельности по цене 20 рублей за диск.
  Покупка не менее 6 дисков такой цене не соответствует, значит, в этом случае была куплена хотя бы одна упаковка. Но что-то ещё, кроме этой упаковке, куплено быть не могло, так как тогда получилось бы, что такая упаковка оптимизирует способ покупки менее чем 6 дисков. Но тогда мы бы и воспользовались таким способом при покупке такого (меньшего 6) количества.
  При покупке 7 дисков должна была использоваться такая же упаковка. То же последовательно (используя каждый раз ранее полученную информацию) мы устанавливаем для 8, 9 и 10 дисков.
  Цена 11 дисков больше, чем 10. Значит, в этой упаковке только 10 дисков. Таким образом, мы узнали параметры одной из упаковок: содержит 10 дисков и стоит 111 рублей.
  Теперь заметим, что цена покупки 24 и 25 дисков – одинаковая, а для покупки 26 – другая.
  При покупке 25 дисков мы не могли использовать одиночных дисков (так как иначе, отказавшись от одного одиночного диска, мы могли бы купить 24 диска на 20 рублей дешевле, чем 25 дисков, а в таблице для этих количеств стоит одинаковая цена). А набрать 25 дисков упаковками по 10 дисков невозможно. Значит, мы установили ещё один тип упаковки: она содержит 25 дисков и стоит 265 рублей. Содержать более 25 дисков такая упаковка не может, так как тогда 26 дисков стоили бы столько же.
  Итак, мы установили 2 типа упаковок:  1) 111 рублей за 10 дисков (11,1 рублей за диск);  2) 265 рублей за 25 дисков (10,6 рублей за диск).
  Поскольку по условию должно быть только два типа упаковок, мы определили все возможные варианты.
  Выясним оптимальную цену покупки 29 дисков. Можно купить три упаковки по 10 дисков, что обойдётся в 333 рубля.
  Покупать одиночные диски нерационально: как только мы купим один одиночный диск (за 20 рублей), нам останется купить 28 дисков, оптимальная цена которых по условию составляет 325 рублей. Итого получится 345 рублей.
  Если мы купим упаковку из 25 дисков, нам останется докупить 4 диска. Из таблицы видно, что дешевле всего их покупать поштучно. Но, как мы только что выяснили, тогда цена будет не меньше 345 рублей.
  Следовательно, первоначально рассмотренный вариант (3 упаковки по 10 дисков) является самым рациональным.


Решение 2

  Построим график зависимости цены одного диска от количества покупаемых оптом дисков.


  Мы видим на графике три "провала" – это и есть то, что нам нужно. Два первых "провала" (минимума) при этом соответствуют одной и той же цене диска 11,1 руб., то есть одному и тому же типу упаковки, а ещё один минимум – другому типу упаковки.


Ответ

В продаже имеются: одиночные диски по цене 20 рублей; упаковки по 10 дисков по цене 111 рублей за упаковку; упаковки по 25 дисков по цене 265 рублей за упаковку. Для покупки не менее 29 дисков необходимо 333 рубля.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2008
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .