В продуктовом магазине есть весы с двумя чашами. На одну чашу весов кладут только продукты, на другую — гири. На чашу для гирь можно положить несколько гирь. Магазину разрешено продавать только целое число килограммов продуктов.
а) Можно ли некоторым набором из пяти гирь отвесить любое целое число килограммов от 1 до 25?
б) Можно ли некоторым набором из четырех гирь отвесить любое целое число килограммов от 1 до 25?
в) Найдите наибольшее значение n такое, что любой вес от 1 до n килограммов можно отвесить каким-нибудь набором из 5 гирь.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Каждая из k гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1,…,H, необходимо H≤2k−1.
k=5
H=25
Шаг 2. Берём гири 1,2,4,…,2k−1. По двоичной записи каждое целое от 1 до 2k−1 представляется суммой некоторого поднабора этих гирь. Следовательно, нижняя граница количества гирь и верхняя граница непрерывного диапазона достигаются.
T=(1;2;4;8;16)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Каждая из k гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1,…,H, необходимо H≤2k−1.
k=4
H=25
Шаг 2. Нет. Необходимое условие или полная конечная область исключает возможность.
Шаг 1. Каждая из k гирь либо берётся, либо не берётся. Непустых подмножеств ровно 2k−1, значит, разных положительных сумм не больше этого числа. Чтобы отвесить все целые массы 1,…,H, необходимо H≤2k−1.
Шаг 2. Берём гири 1,2,4,…,2k−1. По двоичной записи каждое целое от 1 до 2k−1 представляется суммой некоторого поднабора этих гирь. Следовательно, нижняя граница количества гирь и верхняя граница непрерывного диапазона достигаются.