3
$\begingroup$

Original Question:- The standard weights available with a shopkeeper are 1 kg, 2 kg, 4 kg, 8 kg, 16 kg,.... and so on. If the shopkeeper has to weigh 3240 kg, using not more than one weight of each kind and using only one pan of the weighing scale to place the weights, find the number of standard weights required.

So this was the original problem , which I solved by converting 3240 into binary form (110010101000) and checking how many 1's are there to arrive at the required weights combination.

But my question is what if the restriction of putting weights on only 1 pan is removed, and we can use both pans simultaneously to put the weights, how would we able to solve it then ?

$\endgroup$
6
  • $\begingroup$ If restricted to one pan, using only one of each weight is the most efficient no matter what you are weighing (why?). If you can use both pans, then it may be more efficient to "subtract" from $2^{\lfloor\log_2 w \rfloor + 1}$, where $w$ is the weight of the object, but this will depend on $w$. By "efficient," I mean "use the fewest weights." $\endgroup$ Oct 19, 2021 at 20:38
  • $\begingroup$ If you could change the weights, you could use a form of ternary instead of binary $\endgroup$
    – Henry
    Oct 19, 2021 at 20:41
  • $\begingroup$ Very interesting question! One quick observation: the number of weights required to weigh is at most $2\times$ the number of consecutive blocks of ones in the binary representation of $n$. For example, if $n=111000110111$ in binary, you can get away with six weights, since $n=2^{12}-2^9+2^6-2^4+2^3-2^0$. This strategy only saves weights for runs of length $3$ or more. $\endgroup$ Oct 20, 2021 at 2:37
  • $\begingroup$ @MikeEarnest in your binary form we have 3 consecutive blocks of '1s' 111, 11, 111( i.e. having >=2 '1's together) , right ? , how did you arrive at this $n=2^{12}-2^9+2^6-2^4+2^3-2^0$, and what does the subtraction here signifying $\endgroup$
    – Fin27
    Oct 20, 2021 at 13:12
  • $\begingroup$ Just think about how subtraction in binary works. For example, to compute $2^{12}-2^9$, you do $$ \begin{align} &&1000000000000 \\ &&-\phantom{0000}1000000000 \\\hline && 0111000000000 \end{align} $$ $\endgroup$ Oct 20, 2021 at 13:42

1 Answer 1

1
$\begingroup$

When you are able to place weights on either side, we become able to both add and subtract powers of two. This allows for some interesting realizations.

Due to the unique nature of powers of 2, $2^n = 2^{n-1}$. This means that any run of 1s can be replaced by two weights that will subtract to the same value.

This method is fruitless for a run of two, and detrimental even when carried to the extreme with singular 1s being included. However, for any run of 3 1s or more, we can save on weights by using this alternate solution.

For the problem given, there are no runs of length 3 or greater, so there is no way to improve on our count. But in certain circumstances, it can improve our situation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .