Задача 1.
В магазине продаётся 20 товаров, стоимости которых — различные натуральные числа от 1 до 20 рублей. Магазин решил устроить акцию: при покупке любых 5 товаров один из них выдаётся в подарок, причём покупатель сам выбирает, какой товар получит бесплатно. Влад хочет купить все 20 товаров в этом магазине, заплатив как можно меньше. Сколько рублей ему понадобится? (Каждый из 20 товаров продаётся в 1 экземпляре.)
Ответ на Задачу 1.
Ответ: 136 рублей.
Решение:
Влад может воспользоваться акцией не более 4 раз, поэтому он бесплатно приобретёт не более 4 товаров. Суммарная стоимость этих 4 товаров не превосходит 17 + 18 + 19 + 20 рублей. Значит, рублей Владу надо не менее
(1 + 2 + 3 + … + 20) − (17 + 18 + 19 + 20) = 1 + 2 + 3 + … + 16 = 16 ⋅ 17 / 2 = 136
Покажем, что 136 рублей ему точно хватит. Он может совершать покупки товаров со следующими стоимостями: (1, 2, 3, 4, 17), (5, 6, 7, 8, 18), (9, 10, 11, 12, 19), (13, 14, 15, 16, 20). Если Влад в каждой покупке будет брать последний товар бесплатно, то потратит в точности 136 рублей.
