Question

Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 40. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться. Например, при помощи трёх гирек массами 1, 1 и 5 граммов можно отмерить любую целочисленную массу от 1 до 7 граммов по следующей схеме (x – взвешиваемая масса): 1 грамм: x = 1, 2 грамма: x = 1 + 1, 3 грамма: x + 1 + 1 = 5, 4 грамма: x + 1 = 5, 5 граммов: x = 5, 6 граммов: x = 5 + 1, 7 граммов: x = 5 + 1 + 1. Ответом на эту задачу являются несколько целых чисел, записанных через пробел, – массы гирек, при помощи которых можно отмерить любую целочисленную массу от 1 до 40. В наборе должно быть не более 8 чисел. Числа в наборе могут повторяться. Чем меньше гирек будет в предложенном наборе, тем больше баллов вы получите, при условии, что, используя гирьки из данного набора, можно отмерить каждую целочисленную массу от 1 до 40.

Answer 1

Пусть выбраны гирьки с массами M1, M2, ..., Mn и ими удалось массу X.

Тогда имеет место равенство X = a1 * M1 + a2 * M2 + ... + an * Mn,
где ai = 0, если i-ая гирьке не участвовала в взвешиваниях, -1, если лежала на той же чаше весов, что и масса, которкю нужно отмерить, и +1, если на другой чаше весов.

Каждый из коэффициентов принимает одно из трёх значений, тогда при помощи n гирек можно отмерить не более, чем 3^n различных масс. 3^3 < 40 + 1 < 3^4, значит, гирек нужно не менее четырёх. 

Докажем, что взяв гирьки с массами 1, 3, 9 и 27, можно отмерить любую массу от 1 до 40. Будем это делать по индукции, доказав, что при помощи гирек 1, 3, 9, ..., 3^k можно отмерить любую массу от 1 до (3^k - 1)/2.

База индукции. При помощи одной гирьки массой 1 действительно можно отмерить массу 1.
Переход. Пусть для k = k' всё доказано. Докажем и для k = k' + 1.
- Если нужно отмерить массу X <= (3^k' - 1)/2, то это можно сделать при помощи k' гирек.
- Пусть надо отмерить массу (3^k' - 1)/2 < X <= (3^(k' + 1) - 1)/2. Кладём на другую чашу весов гирьку массой 3^k'. Тогда остаётся нескомпенсированная масса X - 3^k' <= (3^k' - 1)/2, которую, по предположению, можно получить. Ура!

Ответ. 1, 3, 9, 27.

Answer 2

Данная задача связана с поиском набора гирек, при помощи которого можно отмерить любую целочисленную массу от 1 до 40 граммов. Чтобы решить эту задачу, нужно использовать принципы комбинаторики и логики.

Подход к решению

Для начала, посмотрим на возможные значения масс гирек. У нас есть гирьки с массами, являющимися целыми числами от 1 до 40 граммов. Мы можем предположить, что нам понадобятся гирьки с массами, которые являются делителями чисел от 1 до 40. Таким образом, мы можем составить список всех делителей чисел от 1 до 40:

1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 7: 1, 7 8: 1, 2, 4, 8 9: 1, 3, 9 10: 1, 2, 5, 10 11: 1, 11 12: 1, 2, 3, 4, 6, 12 ... 40: 1, 2, 4, 5, 8, 10, 20, 40

Поиск набора гирек

Теперь, чтобы найти набор гирек, который позволяет отмерить любую целочисленную массу от 1 до 40 граммов, мы можем использовать следующий алгоритм:

1. Создаем пустой набор гирек. 2. Начинаем с наибольшей гирьки и добавляем ее в набор. 3. Проверяем, можно ли отмерить все числа от 1 до 40 с помощью текущего набора гирек. Если да, то мы нашли решение. 4. Если нельзя отмерить все числа, удаляем последнюю добавленную гирьку и переходим к следующей по убыванию. 5. Повторяем шаги 3-4 до тех пор, пока не найдем решение или не пройдемся по всем гирькам.

Решение задачи

Применяя описанный алгоритм, можно найти несколько наборов гирек, удовлетворяющих условию задачи. Один из возможных наборов гирек, позволяющий отмерить любую целочисленную массу от 1 до 40 граммов, может быть следующим:

Набор гирек: 1 2 3 4 5 6 7 10

Объяснение: - С помощью гирьки массой 1 грамм можно отмерить любую массу от 1 до 1 грамма. - С помощью гирьки массой 2 грамма можно отмерить любую массу от 2 до 2 грамма. - С помощью гирьки массой 3 грамма можно отмерить любую массу от 3 до 3 грамма. - С помощью гирьки массой 4 грамма можно отмерить любую массу от 4 до 4 грамма. - С помощью гирьки массой 5 грамм можно отмерить любую массу от 5 до 5 грамма. - С помощью гирьки массой 6 грамм можно отмерить любую массу от 6 до 6 грамма. - С помощью гирьки массой 7 грамм можно отмерить любую массу от 7 до 7 грамма. - С помощью гирьки массой 10 грамм можно отмерить любую массу от 1 до 40 граммов.

Таким образом, используя данный набор гирек, мы можем отмерить любую целочисленную массу от 1 до 40 граммов.

Другие возможные решения

Существует несколько других наборов гирек, которые также позволяют отмерить любую целочисленную массу от 1 до 40 граммов. Некоторые из них могут быть более оптимальными по количеству гирек. Однако, представленный выше набор является примером решения, удовлетворяющего условиям задачи и имеющего не более 8 чисел в наборе.