Задача 3. ГирькиЕсть чашечные весы без делении. Для взвешивания груза также
Задачка 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.
Тогда имеет место равенство X = a1 * M1 + a2 * M2 + ... + an * Mn,
где ai = 0, если i-ая гирьке не участвовала в взвешиваниях, -1, если лежала на той же чаше весов, что и масса, которкю нужно отмерить, и +1, если на иной чаше весов.
Каждый из коэффициентов воспринимает одно из трёх значений, тогда при помощи n гирек можно отмерить не более, чем 3^n разных масс. 3^3 lt; 40 + 1 lt; 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 lt;= (3^k' - 1)/2, то это можно сделать при помощи k' гирек.
- Пусть надо отмерить массу (3^k' - 1)/2 lt; X lt;= (3^(k' + 1) - 1)/2. Кладём на иную чашу весов гирьку массой 3^k'. Тогда остаётся нескомпенсированная масса X - 3^k' lt;= (3^k' - 1)/2, которую, по предположению, можно получить. Ура!
Ответ. 1, 3, 9, 27.
-
Вопросы ответы
Статьи
Информатика
Статьи
Математика.
Физика.
Математика.
Разные вопросы.
Разные вопросы.
Математика.
Разные вопросы.
Математика.
Физика.
Геометрия.