Любой набор монет

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

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Самая дешёвая выборка
  2. Две линейные границы

    Сначала: Самая дешёвая выборка

  3. Проверка и подсчёт

    Сначала: Две линейные границы

  4. Конструкция

    Сначала: Проверка и подсчёт

  5. Ответ: да

    Сначала: Конструкция

  6. Самая дешёвая выборка

    Сначала: Ответ: да

  7. Две линейные границы

    Сначала: Самая дешёвая выборка

  8. Проверка и подсчёт

    Сначала: Две линейные границы

  9. Конструкция

    Сначала: Проверка и подсчёт

  10. Ответ: нет

    Сначала: Конструкция

  11. Самая дешёвая выборка

    Сначала: Ответ: нет

  12. Две линейные границы

    Сначала: Самая дешёвая выборка

  13. Проверка и подсчёт

    Сначала: Две линейные границы

  14. Ответ

    Сначала: Проверка и подсчёт

Разобранный пример

На столе лежит NN монет по 2 рубля и (800−N)(800-N) монет по 5 рублей (N(N — натуральное число от 1 до 799). Оказалось, что если взять любые 300 монет, то сумма денег, набранная этими монетами, будет не меньше четверти от общей суммы денег на столе.

а) Может ли NN равняться 200?

б) Может ли NN равняться 400?

в) Сколько различных значений может принимать число NN?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Условие для любых kk монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно NN, если первое указанное достоинство меньше, и C−NC-N в обратном случае; в выборку входит минимум этого количества и kk. Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.
Sвсе=2N+5(800−N)S_{\text{все}}=2 N+5 \left(800-N\right)
k=300k=300
Шаг 2. На каждом участке сравниваем минимальную выборку с заданной долей общей суммы, сохраняя строгость неравенства. Учитываем целые границы NN из условия. В таблице приведены все непрерывные целые интервалы допустимых значений.
T=((1;222);(534;799))\mathcal T=\left(\left(1;222\right);\left(534;799\right)\right)
Шаг 3. Проверяем, входит ли заданное NN в найденные интервалы. Для общего количества складываем длины непересекающихся целых интервалов, включая оба конца.
Шаг 4. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
N=200N=200
Smin⁡=900S_{\min}=900
Sвсе=3400S_{\text{все}}=3400
Шаг 5. Да. Указанная конструкция удовлетворяет всем условиям.
Шаг 1. Условие для любых kk монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно NN, если первое указанное достоинство меньше, и C−NC-N в обратном случае; в выборку входит минимум этого количества и kk. Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.
Sвсе=2N+5(800−N)S_{\text{все}}=2 N+5 \left(800-N\right)
k=300k=300
Шаг 2. На каждом участке сравниваем минимальную выборку с заданной долей общей суммы, сохраняя строгость неравенства. Учитываем целые границы NN из условия. В таблице приведены все непрерывные целые интервалы допустимых значений.
T=((1;222);(534;799))\mathcal T=\left(\left(1;222\right);\left(534;799\right)\right)
Шаг 3. Проверяем, входит ли заданное NN в найденные интервалы. Для общего количества складываем длины непересекающихся целых интервалов, включая оба конца.
Шаг 4. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
N=400N=400
Smin⁡=600S_{\min}=600
Sвсе=2800S_{\text{все}}=2800
Шаг 5. Нет. Необходимое ограничение или полный конечный список исключает такой случай.
Шаг 1. Условие для любых kk монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно NN, если первое указанное достоинство меньше, и C−NC-N в обратном случае; в выборку входит минимум этого количества и kk. Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.
Sвсе=2N+5(800−N)S_{\text{все}}=2 N+5 \left(800-N\right)
k=300k=300
Шаг 2. На каждом участке сравниваем минимальную выборку с заданной долей общей суммы, сохраняя строгость неравенства. Учитываем целые границы NN из условия. В таблице приведены все непрерывные целые интервалы допустимых значений.
T=((1;222);(534;799))\mathcal T=\left(\left(1;222\right);\left(534;799\right)\right)
Шаг 3. Проверяем, входит ли заданное NN в найденные интервалы. Для общего количества складываем длины непересекающихся целых интервалов, включая оба конца.
Шаг 4. Записываем найденное значение, достигаемое приведённым вариантом.
488488

Открыть задачу целиком

Попробовать самостоятельно