Реши задачу номер 13

Задача 13: есть чашечные весы без стрелок. Гири можно ставить только на одну чашку. Нужно подобрать массы четырех гир так, чтобы с их помощью можно было взвесить любое целое число килограммов от 1 до 15.

Пояснение и решение:

• Поскольку гири кладутся только на одну чашку, масса объекта m может быть взята равной сумме некоторых гирь. То есть возможны все суммы подмножеств четырех гир.
• С четвертью гирями существует 2^4 − 1 = 15 ненулевых сумм, поэтому теоретически можно получить все числа от 1 до 15, если суммы подмножеств будут различны и заполнять диапазон 1…15.
• Чтобы все 15 целых чисел от 1 до 15 можно было получить без пропусков и без повторений, массы гир должны образовывать систему поразрядной двоичной записи. Единственный набор, который это обеспечивает, — 1, 2, 4 и 8 кг.
  • Обоснование: начнем с наименьшей гири. чтобы можно было измерить 1 кг, первая гиря должна быть 1 кг. Далее, чтобы можно было измерить 2 кг, вторая гиря должна быть не более 2 кг; чтобы сохранить полноту покрытия и избежать пропусков/повторов, выбираем 2 кг. Аналогично третья гиря должна быть 4 кг, четвертая — 8 кг.
• Проверка: каждое число от 1 до 15 можно получить как сумма некоторых из гир:
  • 1 = 1
  • 2 = 2
  • 3 = 1 + 2
  • 4 = 4
  • 5 = 1 + 4
  • 6 = 2 + 4
  • 7 = 1 + 2 + 4
  • 8 = 8
  • 9 = 1 + 8
  • 10 = 2 + 8
  • 11 = 1 + 2 + 8
  • 12 = 4 + 8
  • 13 = 1 + 4 + 8
  • 14 = 2 + 4 + 8
  • 15 = 1 + 2 + 4 + 8

Вывод: массы гир для задачи — 1 кг, 2 кг, 4 кг и 8 кг. С их помощью можно взвесить любое целое число от 1 до 15 кг, кладя нужные гири на одну чашу против объекта.