И снова гиpи, взвешивания!

[bitcoin]

На овощном рынке работает Егор. Он мoжeт иcпoльзoвaть чeтыpe гиpи для взвeшивaния любoгo цeлoгo чиcлa килoгpaммoв oт 1 дo 40 включитeльнo на чашечных весах без стрелки (гиpи мoжнo paзмeщaть нa oбeиx чaшax вecoв).
А) Укaжитe пpимep тaкoгo нaбopa гиpь.
Б) Вoзмoжнo ли oбoйтиcь тpeмя гиpями?
В) Скoлькo гиpь минимaльнo пoнaдoбитcя, ecли гиpи мoжнo клacть тoлькo нa oднy чaшy вecoв?

У меня есть догадки:

A) $1,3,9,27$. Вроде как такой набор вполне подойдет.
Б) Нельзя. Тремя можно только взвесить набор до 13 кг, например гирями $1,3,9$. Но как доказать строго?
В) Если гири можно класть только на одну чашу весов, минимально понадобится 6 гирь, массой 1 кг, 2 кг, 4 кг, 8 кг, 16 кг и 32 кг. Но хочется какое-то лаконичное обоснование получить, а не просто перебирать варианты.

Число $40$ в троичной системе будет так выглядеть $40_{10} = 1111_3$ Интуитивно предполагаю, что может троичная система в этом контексте вот так может использоваться? В троичной системе счисления есть цифры 0, 1 и 2. Но в нашем случае лучше, наверное сделать, чтобы цифра 1 означала, что гиря на одной чаше, -1 (или 2 в троичной системе) означает, что гиря на другой чаше, а 0 означает, что гиря не используется.
Но все равно не очень ясно - как это помогает.
Для пункта В интуитивно кажется, что нужна двоичная система, так как там только на одну чашу можно гирю положить. Но не могу все это как-то связно соединить, не получается догадаться. Сможете, пожалуйста, помочь с этим?

[iifat]

Ну, расположение гирь на весах естественно представляется набором коэффициентов -1, 0, 1. Безотносительно представления такого набора числом в сдвинутой троичной системе, сколько всего наборов можно составить из трёх чисел -1, 0, 1 (учитывая порядок)? Сколько макисмально различных весов можно представить набором таких наборов ;)?

bitcoin в сообщении #1646906 писал(а):

Интуитивно предполагаю, что может троичная система в этом контексте вот так может использоваться?

Попробуйте доказать вашу интуицию. Начните, например, с $5=12_3$.

[bitcoin]

iifat в сообщении #1646909 писал(а):

сколько всего наборов можно составить из трёх чисел -1, 0, 1 (учитывая порядок)?

Спасибо большое! $3!=6$ вариантов.

iifat в сообщении #1646909 писал(а):

Сколько макисмально различных весов можно представить набором таких наборов ;)?

Может быть $A_{40}^3=40\cdot 39\cdot 38$? Я этот вопрос понял так. Есть массы $1,2,3,4,...,40$, из них нам нужно выбрать три, при этом важен порядок. И каждой выбранной тройке $(a,b,c)$ масс можно поставить в соотвествие одну из 6 перестановок троек вида $(-1,0,1)$

iifat в сообщении #1646909 писал(а):

Попробуйте доказать вашу интуицию. Начните, например, с $5=12_3$.

А как начать? Если у нас есть максимальная масса 5, то массы $1,2,3,4,5$ можно получить двусторонними взвешиваниями гирь $1,2,3$. Меньше не получается. Но не очень понятно -- как здесь пригодилась троичная система=)

[мат-ламер]

iifat в сообщении #1646909 писал(а):

учитывая порядок)

Причём тут порядок?

bitcoin в сообщении #1646906 писал(а):

Б) Вoзмoжнo ли oбoйтиcь тpeмя гиpями?

Итак, у вас три гири. Для каждой из трёх гирь есть три возможности - попасть на левую чашку, на правую и не участвовать во взвешивании. Значит, всего нам доступно для взвешивания $3^3=27$ вариантов весов. Это, безотносительно того, какие веса гирь. Более того, в худшем случае варианты тут могут повторяться. Так что имеем не более $27$ вариантов. Они никак не покрывают $40$ нужных нам.

bitcoin в сообщении #1646906 писал(а):

В) Скoлькo гиpь минимaльнo пoнaдoбитcя, ecли гиpи мoжнo клacть тoлькo нa oднy чaшy вecoв?

Абсолютно то же самое. Пять гирь дают $2^5=32$ варианта, что нам не подходит. Шесть гирь нас удовлетворят. Все числа от $1$ до $40$ записываются не более шестью цифрами в двоичной системе исчисления.

[Евгений Машеров]

bitcoin в сообщении #1646906 писал(а):

Но в нашем случае лучше, наверное сделать, чтобы цифра 1 означала, что гиря на одной чаше, -1 (или 2 в троичной системе) означает, что гиря на другой чаше, а 0 означает, что гиря не используется.

Это называется "троично-симметричная система". Интересна тем, что в ней не нужен отдельный знак числа. И очень хорошо с округлением.

[bitcoin]

мат-ламер в сообщении #1646948 писал(а):

Итак, у вас три гири. Для каждой из трёх гирь есть три возможности - попасть на левую чашку, на правую и не участвовать во взвешивании. Значит, всего нам доступно для взвешивания $3^3=27$ вариантов весов. Это, безотносительно того, какие веса гирь. Более того, в худшем случае варианты тут могут повторяться. Так что имеем не более $27$ вариантов. Они никак не покрывают $40$ нужных нам.

Спасибо большое, все понял. Можно даже сказать, что точно меньше 27 вариантов, потому как вариант не взять ни одну из гирь не может быть исполнен, насколько я понял. Что-то я подзатупил на ровном месте. Правда, по ощущениям, здесь как-то притянута троичная система, но наверное я ошибаюсь.

[iifat]

мат-ламер в сообщении #1646948 писал(а):

Причём тут порядок?

Ну, при том, что (1, 1, 0) это совсем не то что (0, 1, 1).

[Евгений Машеров]

В общем, это задача представления чисел в некоторой разрядной системе счисления. При этом, если гири можно класть лишь на одну чашу весов, это двоичная система (1 - положили, 0 - не положили). А если на обе, то троично-симметричная, с цифрами $\bar{1}, 0, 1$ где первый символ равен минус единице а для весов означает помещение гири в чашу к взвешиваемому грузу. Минимальность следует из отсутствия избыточности.

[мат-ламер]

bitcoin в сообщении #1646973 писал(а):

Можно даже сказать, что точно меньше 27 вариантов, потому как вариант не взять ни одну из гирь не может быть исполнен, насколько я понял.

Вы абсолютно правы! Ведь:

мат-ламер в сообщении #1646948 писал(а):

варианты тут могут повторяться.

Во-первых, мы должны отбросить один вариант, когда ни одна из гирь не ставится на весы. Кроме того, варианты у нас идут парочками, в зависимости от того, на какой из чашки весов находится груз (симметрия). И нас тут интересует лишь один вариант из пары. Итого у нас получается $(3^3-1)/2=13$ вариантов.

bitcoin в сообщении #1646973 писал(а):

Правда, по ощущениям, здесь как-то притянута троичная система

Абсолютно верно! Если мыслить в этом направлении, то у нас получается $3^0+3^1+3^2=1+3+9=13$ вариантов. А вот подумать о том, почему этот результат в точности совпадает с ранее полученным, почему он будет совпадать для любого количества гирь и при чём тут сумма геометрической прогрессии, я оставляю вам.

[bitcoin]

мат-ламер в сообщении #1647051 писал(а):

Абсолютно верно! Если мыслить в этом направлении, то у нас получается $3^0+3^1+3^2=1+3+9=13$ вариантов. А вот подумать о том, почему этот результат в точности совпадает с ранее полученным, почему он будет совпадать для любого количества гирь и при чём тут сумма геометрической прогрессии, я оставляю вам.

Спасибо большое Если кратко, мне идея построения оценки во всех пунктах идеально понятна. А вот с примерами -- туговато, не очень. Про обобщение на $n$ гирь напишу ниже.

Если $n$ гирь, то получается $\frac{3^n-1}{3-1}$ вариантов (вычли вариант с отсутсвтующиими гирями, а также парные варианты). А это каким-то чудесным образом получается в точности формула геометрической прогрессии для суммы $n$ чисел, а именно $\frac{3^n-1}{3-1}=1+3+3^2+...+3^{n-1}$. И здесь возникает чудесная мысль=) Почему бы для того, чтобы определить минимальное количество гирь, необходимых для того, чтобы уравновешивать (используя 2 чаши) массы $1,2,3,.., \frac{3^n-1}{2}$ не взять $n$ гирь массами $1,3^2,...,3^{n-1}$. И их действительно хватит=) Вроде бы так обобщается. Но есть один нюанс. Мне очень хорошо понятна идея - откуда взялась идея с оценкой, прям идеально понятно. Но подбор примера для меня все еще напоминает танцы у костра с бубном, авось смотрите, а тут работает все хорошо и именно эти $n$ гирь решают наш вопрос, а не какой-то другой набор из других $n$ гирь=) Более того, нужно проверять этот набор вручную. То есть происхождение примера и его проверка - вызывает вопросы=) И еще, есть немного странный вопрос - мы исключаем симметричные варианты в том числе из-за того, что взвешиваемое тело мы тоже можем класть на любую чашу весов? Также идея с оценкой очень хорошо понятна, если задействовать только одну чашу весов и понятно как ее обобщить. Но подбор примера со степенями двойки тоже для меня - танец у костра с бубнами, ведь нужно не только угадать такой пример, но еще вручную проверять, что именно эти гири подходят! Эх.

P.S. Почему-то задача с гирями на 2 чаши весов мне напоминает задачу с $3^n$ монетами, среди которых одна фальшивая (легче настоящей), когда требуется $n$ взвешиваний.

[wrest]

bitcoin в сообщении #1647113 писал(а):

откуда взялась идея с оценкой, прям идеально понятно. Но подбор примера для меня все еще напоминает танцы у костра с бубном

Да, оценка это одно, а работающий как надо пример - совсем другое.
Вас же в задаче не спрашивают про взвешивание 40 любых разных весов на ваш выбор. Спрашивают же конкретно: минимум от 1 до 40, с шагом в единицу. Оценками вы понимаете что тремя гирями - никак. А вот подбор четырёх гирь которыми можно с шагом в единицу взвешивать - это самостоятельная задача.

[Евгений Машеров]

bitcoin в сообщении #1647113 писал(а):

Почему-то задача с гирями на 2 чаши весов мне напоминает задачу с $3^n$ монетами, среди которых одна фальшивая (легче настоящей), когда требуется $n$ взвешиваний.

А вот на подумать: есть 12 монет, фальшивая отлична по весу, но неизвестно, тяжелее или легче. Найти за 3 взвешивания.

(Оффтоп)

Говорят, во время Второй Мировой эта задача была популярна в американских военных НИИ, и руководитель военной науки, узнав, сколько времени потрачено на её решение, приказал перевести на немецкий и сбросить над немецкими военными НИИ...

[мат-ламер]

bitcoin в сообщении #1647113 писал(а):

Мне очень хорошо понятна идея - откуда взялась идея с оценкой, прям идеально понятно. Но подбор примера для меня все еще напоминает танцы у костра с бубном, авось смотрите, а тут работает все хорошо и именно эти $n$ гирь решают наш вопрос, а не какой-то другой набор из других $n$ гирь=) Более того, нужно проверять этот набор вручную. То есть происхождение примера и его проверка - вызывает вопросы=)

Рассмотрим вариант с тремя гирями. Мы оценили, что тремя гирями мы можем взвесить 13 различных весов. Вопрос 1 - какой набор гирь взять, чтобы можно было взвесить все целочисленные веса от 1 до 13 кг. Здесь поможет нам обычная троичная система исчисления. Возникает гипотеза, что нам достаточно гири весом 1, 3 и 9 кг. Теперь возникает вопрос 2. Как нам убедиться попроще, что нам этих гирь достаточно. Записываем все наши веса от 1 до 13 в обычной троичной системе исчисления. Далее полагаем, что первой цифре соответствует самая большая гиря, второй цифре средняя гиря, третьей цифре - самая маленькая гиря. Затем, если в числе присутствует цифра 0 - значит ставим гирю на левую чашу весов. Если 1 - вообще не ставим гирю на весы. Если 2 - ставим гирю на правую чашу весов. Тем самым мы быстро получаем все возможные варианты взвешивания.

bitcoin в сообщении #1647113 писал(а):

И еще, есть немного странный вопрос - мы исключаем симметричные варианты в том числе из-за того, что взвешиваемое тело мы тоже можем класть на любую чашу весов?

Вот именно!

bitcoin в сообщении #1647113 писал(а):

Но подбор примера со степенями двойки тоже для меня - танец у костра с бубнами, ведь нужно не только угадать такой пример, но еще вручную проверять, что именно эти гири подходят! Эх.

Здесь прокатывает та же идея, что и с троичной системой. Только всё гораздо проще, ибо для каждой гири у нас тут только два возможных варианта.

[wrest]

мат-ламер в сообщении #1647159 писал(а):

Тем самым мы быстро получаем все возможные варианты взвешивания.

Осталось доказать единственность набора из трёх гирь $\{1,3,9\}$