Реши задачу номер 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 кг, кладя нужные гири на одну чашу против объекта.