Question

есть купюры достоинством 50,100,500,и 1000 рублей.какое минимальное количество таких купюр необходимо и достаточно взять, чтобы при абсолютно любом раскладе,всегда нашлись 5 купюр одного достоинства?

Answer 1

Для решения этой задачи давайте воспользуемся методом исключения. Мы хотим найти минимальное количество купюр каждого достоинства, которые обеспечат нахождение хотя бы 5 купюр одного достоинства в любом случае.

Давайте рассмотрим ситуацию, когда у нас есть по одной купюре каждого номинала: 50, 100, 500 и 1000 рублей. Всего у нас 4 купюры.

Если мы возьмем 4 купюры по одной, в худшем случае (наименее выгодном для нас), нам понадобится найти 5 купюр одного достоинства. Попробуем создать такой "наихудший" случай.

Предположим, мы хотим найти 5 купюр номиналом в 50 рублей. Мы можем составить сумму, не включая 50 рублей, с помощью других купюр. Это возможно:

- Максимальная сумма, которую мы можем получить, не включая 50 рублей: \(100 + 500 + 1000 = 1600\). - Мы хотим минимизировать количество купюр одного достоинства, так что будем использовать наибольшие купюры для получения максимальной суммы: \(1000 + 1000 = 2000\).

Теперь добавляем 50 рублей: \(2000 + 50 = 2050\). Таким образом, мы можем составить любую сумму, начиная от 50 до 2050 рублей, используя эти 4 купюры.

Это значит, что даже при худшем раскладе, где мы стараемся максимально разнообразить номиналы купюр, у нас не получается обеспечить нахождение 5 купюр одного достоинства.

Таким образом, для гарантированного нахождения 5 купюр одного достоинства в любом случае нам необходимо взять минимум 5 купюр одного номинала.