Задача 4. Гирьки У ювелира есть весы с двумя чашками, он может определять равны ли массы грузов, лежащих на двух чашках, а если не равны – то на какой чашке лежит более легкий груз. Масса ювелирного изделия, которую нужно определить ювелиру, является целым числом от 1 до 25 грамм. Ювелир должен запасти набор гирек (их массы также должны быть целыми числами), используя которые он может определить любую возможную целочисленную массу от 1 до 25 грамм. Для определения массы ювелир может производить любое число взвешиваний, может использовать все или только часть набора гирек, может класть гирьки на разные чашки весов и т. д. Определите набор гирек, содержащий минимальное возможное число гирек, используя который можно определить любую возможную целочисленную массу от 1 до 25. В ответе нужно записать массы гирек в подготовленном наборе через пробел. За правильный набор из трёх гирек вы получите 10 баллов, из четырёх гирек – 5 баллов, из пяти гирек – 2 балла. Например, если нужно было бы определить массу ювелирного изделия от 1 до 3 грамм, то ювелиру достаточно было иметь одну гирьку массой 2 грамма. Тогда нужно положить на одну чашку весов изделие неизвестной массы х, а на другую чашку весов гирьку, и по результату взвешивания х < 2, x = 2 или х > 2 станет понятно значение х. Если же требуется определить целочисленную массу от 1 до 5 грамм, то необходимо две гирьки. Подойдёт, например, набор из гирек массами 3 и 4. Пусть х – ювелирное изделие целочисленной массы от 1 до 5. Тогда массы 3, 4, 5 можно определить при помощи взвешиваний х = 3, x = 4 и х > 4. Массу 1 грамм можно определить при помощи равенства х + 3 = 4 (на одну чашу кладётся изделие и гирька в 3 грамма, на другую чашу гирька в 4 грамма). Массу в 2 грамма можно определить, например, по условию х <3 (на одну чашу весов кладётся изделие, на другую – гирька в 3 грамма), а также проверив при помощи ранее описанного алгоритма, что х ≠ 1. Решением задач 5–7 является программа, написанная на одном из языков программирования.

Решение:

Для определения целочисленной массы от 1 до 25 грамм с минимальным количеством гирек, нам нужно выбрать гирьки так, чтобы любая сумма или разность их масс могла образовать любое число в этом диапазоне. Это задача на систему счисления с основанием 3 (троичная система).*

В троичной системе счисления с использованием цифр {–1, 0, 1} можно представить любое число. В нашем случае, гирьки будут соответствовать степеням тройки:

• 1-я гирька: \( 3^0 = 1 \) грамм.
• 2-я гирька: \( 3^1 = 3 \) грамма.
• 3-я гирька: \( 3^2 = 9 \) грамм.
• 4-я гирька: \( 3^3 = 27 \) грамм.

С помощью этих гирек мы можем представить следующие массы:

• 1 грамм: 1
• 2 грамма: 3 – 1
• 3 грамма: 3
• 4 грамма: 3 + 1
• 5 грамм: 9 – 3 – 1
• ...
• 25 грамм: 27 – 1 – 1

Однако, в задаче сказано, что гирьки могут лежать на разных чашках, что позволяет использовать взвешивание с положительными и отрицательными весами (аналог троичной системы с цифрами {-1, 0, 1}).

Чтобы определить массы от 1 до 25, нам нужно найти такой набор гирек, чтобы любая масса могла быть представлена как \( ± a_1 ± a_2 ± ³ ± ´ ± ... \) где \( a_i \) — массы гирек. Максимальная масса, которую можно измерить с \(n\) гирьками, использующими троичное представление (с возможностью класть гирьки на обе чаши), равна \( \frac{3^n - 1}{2} \).

Нам нужно, чтобы \( \frac{3^n - 1}{2} ≥ 25 \), что означает \( 3^n - 1 ≥ 50 \), то есть \( 3^n ≥ 51 \).

При \( n=1 \): \( 3^1 = 3 \) (максимум 1 грамм)

При \( n=2 \): \( 3^2 = 9 \) (максимум 4 грамма)

При \( n=3 \): \( 3^3 = 27 \) (максимум 13 грамм)

При \( n=4 \): \( 3^4 = 81 \) (максимум 40 грамм)

Следовательно, нам нужно 4 гирьки. Массы гирек будут являться степенями тройки: \( 3^0, 3^1, 3^2, 3^3 \).

Набор гирек: 1, 3, 9, 27. Однако, с этими гирьками мы можем измерить до \( 1+3+9+27 = 40 \) грамм. Нам нужно измерить до 25 грамм.

Если нам нужно измерить до 25 грамм, и мы используем систему с основанием 3, где гирьки могут быть как с плюсом, так и с минусом, то минимальный набор гирек будет:

1 грамм (\( 3^0 \)) - можно измерить 1.

3 грамма (\( 3^1 \)) - можно измерить 1, 3, 3-1=2.

9 грамм (\( 3^2 \)) - можно измерить 1, 2, 3, 9, 9-1=8, 9-2=7, 9-3=6, 9+1=10, 9+2=11, 9+3=12.

С тремя гирьками (1, 3, 9) мы можем измерить до \( \frac{3^3-1}{2} = \frac{26}{2} = 13 \) грамм.

Для 25 грамм нам понадобится 4 гирьки. Массы гирек будут: 1, 3, 9, 27. Однако, 27 грамм — это больше, чем нам нужно. Минимальный набор для 25 грамм — это гирьки, которые позволяют покрыть все значения.

Проверим набор 1, 3, 9. Максимальная измеримая масса: 1+3+9 = 13. Этого недостаточно.

Проверим набор 1, 3, 9, 27. Максимальная измеримая масса: 1+3+9+27 = 40. Это больше, чем 25. Можем ли мы измерить 25? Да, например, 27 - 1 - 1 = 25. Но это требует двух гирек по 1 грамму, а у нас одна. Или 27 - 3 + 1 = 25.

С четырьмя гирьками (1, 3, 9, 27) мы можем измерить все числа до 40. Так как нам нужно до 25, то 4 гирьки — это то, что нужно.

Минимальный набор гирек для измерения массы от 1 до N, используя взвешивание на двух чашах, состоит из гирек с массами \( 3^0, 3^1, ..., 3^{n-1} \), где \( n \) — минимальное число, такое что \( \frac{3^n - 1}{2} ≥ N \).

В нашем случае \( N=25 \). Мы нашли, что \( n=4 \).

Массы гирек: \( 3^0=1 \), \( 3^1=3 \), \( 3^2=9 \), \( 3^3=27 \). Таким образом, набор 1, 3, 9, 27 позволяет измерить массы до 40. Чтобы измерить 25, мы можем использовать, например, 27 - 3 + 1 = 25 (27 на одной чаше, 3 и 1 на другой).

Если в ответе должно быть ровно 25, то нужно найти минимальный набор.

Если мы возьмем гирьки 1, 3, 9, то максимум, что мы можем измерить - это 13. С четырьмя гирьками 1, 3, 9, 27, мы можем измерить от 1 до 40.

Для 25 грамм, набор 1, 3, 9, 27 подходит. Однако, есть более точное решение, которое предполагает, что набор должен состоять из гирек, где максимальная измеримая масса равна 25.

Используем гирьки 1, 3, 9. Максимальная измеряемая масса: 13. Не подходит.

Используем гирьки 1, 3, 9, 27. Максимальная измеряемая масса: 40. Нам нужно 25. Минимальный набор гирек для диапазона от 1 до \( M \) - это \( n \) гирек, где \( M ≤ \frac{3^n-1}{2} \).

Для \( M=25 \), \( \frac{3^n-1}{2} ≥ 25 ⇒ 3^n - 1 ≥ 50 ⇒ 3^n ≥ 51 \). Это выполняется при \( n=4 \).

Набор гирек: 1, 3, 9, 27. Это позволяет измерить все массы от 1 до 40.

Если же мы хотим измерить ровно 25, то нам нужен набор, где максимальная измеряемая масса — 25.

Массы гирек: 1, 3, 9. Можно измерить: 1, 3, 9, 3+1=4, 9+1=10, 9+3=12, 9+3+1=13. Максимум 13.

С гирьками 1, 3, 9, 27. Максимум 40.

Поскольку задача говорит о минимальном возможном числе гирек, и мы можем измерить до 25, то 4 гирьки (1, 3, 9, 27) являются оптимальными, так как они покрывают весь диапазон до 25 и даже больше.

Пример:

1 грамм: 1

2 грамма: 3 - 1

3 грамма: 3

4 грамма: 3 + 1

...

13 грамм: 9 + 3 + 1

14 грамм: 27 - 9 - 3 - 1

25 грамм: 27 - 3 + 1

30 грамм: 27 + 3

40 грамм: 27 + 9 + 3 + 1

Ответ: 1 3 9 27