В продуктовом магазине есть весы с двумя чашами. На одну чашу весов кладут только продукты, на другую — гири. На чашу для гирь можно положить несколько гирь. Магазину разрешено продавать только целое число килограммов продуктов.
а) Можно ли некоторым набором из пяти гирь отвесить любое целое число килограммов от 1 до 25?
б) Можно ли некоторым набором из четырех гирь отвесить любое целое число килограммов от 1 до 25?
в) Найдите наибольшее значение такое, что любой вес от 1 до килограммов можно отвесить каким-нибудь набором из пяти гирь.
Развёрнутое задание второй части — реши на бумаге и сверься с разбором
Гири кладутся только на одну чашу, поэтому отвесить можно ровно те веса, которые равны суммарной массе какого-нибудь непустого набора гирь.
а) Да, можно. Возьмём гири массой и кг. Покажем, что ими отвешивается любой целый вес от до кг, а значит, и от до кг. Гирями получаются все веса от до (левая часть таблицы), а добавляя к этим наборам гирю кг, получаем все веса от до (правая часть); вес — одна гиря кг:
По сути это запись числа в двоичной системе: каждое число от до записывается не более чем пятью двоичными цифрами, то есть раскладывается в сумму различных степеней двойки из .
б) Нет, нельзя. Для каждой из четырёх гирь есть два варианта: положить её на чашу или нет. Поэтому всего наборов , и один из них пустой (вес ). Непустых наборов , а значит, различных положительных весов не больше (разные наборы могут давать одинаковый вес, но это только уменьшает число весов). А различных весов от до кг — штук, и .
в) Оценка. Из пяти гирь можно составить набора, из них непустых . Поэтому различных положительных весов не больше . Если отвешиваются все веса , то это различных весов, и .
Пример. Набором гирь кг отвешивается любой вес от до кг — это видно из таблицы в пункте а). Значит, достигается.
Ответ: а) да; б) нет; в) .