Взвешивание набором гирь

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

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

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

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

  1. Количество подмножеств гирь
  2. Достижение границы

    Сначала: Количество подмножеств гирь

  3. Ответ: да

    Сначала: Достижение границы

  4. Количество подмножеств гирь

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

  5. Ответ: нет

    Сначала: Количество подмножеств гирь

  6. Количество подмножеств гирь

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

  7. Достижение границы

    Сначала: Количество подмножеств гирь

  8. Ответ

    Сначала: Достижение границы

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

В продуктовом магазине есть весы с двумя чашами. На одну чашу весов кладут только продукты, на другую — гири. На чашу для гирь можно положить несколько гирь. Магазину разрешено продавать только целое число килограммов продуктов.

а) Можно ли некоторым набором из пяти гирь отвесить любое целое число килограммов от 1 до 25?

б) Можно ли некоторым набором из четырех гирь отвесить любое целое число килограммов от 1 до 25?

в) Найдите наибольшее значение nn такое, что любой вес от 1 до nn килограммов можно отвесить каким-нибудь набором из 5 гирь.

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

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

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

Шаг 1. Каждая из kk гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−12^{k}-1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1, …, H1,\,\ldots,\,H, необходимо H≤2k−1H\leq 2^{k}-1.
k=5k=5
H=25H=25
Шаг 2. Берём гири 1, 2, 4, …, 2k−11,\,2,\,4,\,\ldots,\,2^{k-1}. По двоичной записи каждое целое от 1 до 2k−12^{k}-1 представляется суммой некоторого поднабора этих гирь. Следовательно, нижняя граница количества гирь и верхняя граница непрерывного диапазона достигаются.
T=(1;2;4;8;16)\mathcal T=\left(1;2;4;8;16\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Каждая из kk гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−12^{k}-1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1, …, H1,\,\ldots,\,H, необходимо H≤2k−1H\leq 2^{k}-1.
k=4k=4
H=25H=25
Шаг 2. Нет. Необходимое условие или полная конечная область исключает возможность.
Шаг 1. Каждая из kk гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−12^{k}-1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1, …, H1,\,\ldots,\,H, необходимо H≤2k−1H\leq 2^{k}-1.
Шаг 2. Берём гири 1, 2, 4, …, 2k−11,\,2,\,4,\,\ldots,\,2^{k-1}. По двоичной записи каждое целое от 1 до 2k−12^{k}-1 представляется суммой некоторого поднабора этих гирь. Следовательно, нижняя граница количества гирь и верхняя граница непрерывного диапазона достигаются.
T=(1;2;4;8;16)\mathcal T=\left(1;2;4;8;16\right)
Шаг 3. Записываем найденное значение.
3131

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

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