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

bitcoin · 19/04/18 207

На овощном рынке работает Егор. Он м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 · 16/02/13 4195 Владивосток

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

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

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

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

bitcoin · 19/04/18 207

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$ . Меньше не получается. Но не очень понятно -- как здесь пригодилась троичная система=)

мат-ламер · 30/01/09 7068

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$ записываются не более шестью цифрами в двоичной системе исчисления.

Евгений Машеров · 11/03/08 9904 Москва

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

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

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

bitcoin · 19/04/18 207

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

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

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

iifat · 16/02/13 4195 Владивосток

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

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

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

Евгений Машеров · 11/03/08 9904 Москва

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

мат-ламер · 30/01/09 7068

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

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

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

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

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

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

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

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

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

bitcoin · 19/04/18 207

мат-ламер в сообщении #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 · 05/09/16 12061