Задача 3. Гирьки Есть чашечные весы без делений. Для взвешивания груза также можно...

Question

Задача 3. Гирьки
Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 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.

Comments

Помогите пожалуйста

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' гирек. <br>- Пусть надо отмерить массу (3^k' - 1)/2 < X <= (3^(k' + 1) - 1)/2. Кладём на другую чашу весов гирьку массой 3^k'. Тогда остаётся нескомпенсированная масса |X - 3^k'| <= (3^k' - 1)/2, которую, по предположению, можно получить. Ура!<br>
Ответ. 1, 3, 9, 27.