Олимпиадная задача 18 (Взвешивания)

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

Условие:
Вес каждой гирьки набора — нецелое число грамм. Ими можно уравновесить любой целый вес от 1г до 40г (гири кладутся на одну чашку весов, измеряемый вес — на другую). Каково наименьшее число гирь в таком наборе?
Весы для взвешивания грузов в 40г, по мнению автора
Весы для взвешивания грузов в 40г, по мнению автора

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

Решение:

Упорядочим гири в порядке возрастания.

Сумма 1 и 2 гири должна равняться 1г (иначе единицу никак нельзя будет получить, или для этого потребуется больше гирь).

Добавим третью гирю. Суммарный вес будет не более 3г, так как 3-я гиря весит меньше 2г (иначе никак нельзя получить 2г).

Аналогично 4-я гиря легче 3г (сумма легче 6г), 5-я гиря легче 6г (сумма легче 12г), 6-я гиря легче 12г (сумма легче 24), 7-я гиря легче 24г (сумма легче 48г). Таким образом меньше чем 7-ю гирями уравновесить все различные веса от 1г до 40г нельзя.

Приведем пример, как это сделать 7-ю гирями.

Веса гирь: 0.5г, 0.5г, 1.5г, 2.5г, 5.5г, 10.5г, 20.5г.

Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!