9
$\begingroup$

You are an ancient merchant, and you need to weigh out many different items of many different weights. To do so, you'll design a scale to weigh objects. Unlike a standard scale, your scale will have four different pans, at your choice of four distances from the fulcrum.

You will also select four different standardized masses, of weights of your choice.

Your goal is to be able to weigh out every possible integer weight from 1 gram up to N grams, for the largest possible value of N.

To "weigh out" a weight means that there must be some arrangement of the weight and your standardized masses on the pans of your scale such that the scale exactly balances. Also, assume that your scale exactly balances when all four pans are empty.

If your scale only had 2 pans equidistant from the fulcrum, the optimal value of N would be 40. With 4 pans, how much higher can you go?

Edit: There was a bug in the computer program I used to find my best solution. I have fixed it, and am refinding a best solution.

$\endgroup$
9
  • 1
    $\begingroup$ I'm not sure it matters, but should we be assuming the four pans must lie in a straight line? $\endgroup$
    – msh210
    Feb 7 at 7:41
  • 1
    $\begingroup$ Do you know the optimal solution? I have the impression that with 4 weights and 4 pans this will be a big enough number to make this infeasible for pen and paper. $\endgroup$
    – quarague
    Feb 7 at 8:00
  • $\begingroup$ @msh210 Yes, a straight line. $\endgroup$
    – isaacg
    Feb 7 at 16:53
  • $\begingroup$ @quarague I wrote a computer program, I believe it's found the best solution. $\endgroup$
    – isaacg
    Feb 7 at 16:53
  • 1
    $\begingroup$ I learned a new word - fulcrum :) $\endgroup$ Feb 8 at 8:45

1 Answer 1

5
$\begingroup$

Here is my solution. I do not know if this is optimal or not.

I can achieve $N=3(5^4-1)/4=468.$

Here is the method.

We specify the locations of the pans by their $x$-coordinates, where $x=0$ is the fulcrum. The pans should be placed at $x=-1,1,2,3$. The measures of the weights are $1,5,5^2$ and $5^3$.

Note that any integer in the range between $-(5^4-1)/4$ and $+3(5^4-1)/4$ can be uniquely written in the form $\sum_{i=0}^3 d_i5^i$, where $d_i\in \{-1,0,1,2,3\}$ (see Lemma). This allows you to weigh any item with weights in that range. Place the item to be weighed in the pan at $x=-1$, then for each $i\in \{0,1,2,3\}$, place the weight with measure $5^i$ in the pan at $x=d_i$. If $d_i=0$, you simply omit that weight.

Proof of Lemma:

It is well-known that every number in the range $0$ to $5^n-1$ can be uniquely written in the form $\sum_{i=0}^{n-1}a_i5^i$, with each $a_i\in \{0,1,2,3,4\}$. This is just how the base-5 system works. That is, $$0\le x\le 5^n-1\quad \iff \quad x=\sum_{i=0}^{n-1}a_i5^i$$ Now, subtract $1+5+\dots+5^{n-1}=(5^n-1)/4$ from both sides. We see that $$-\frac{5^n-1}4\le x\le \frac{3(5^n-1)}4\quad \iff\quad x=\sum_{i=0}^{n-1}(a_i-1)5^i$$ Conclude by letting $d_i=a_i-1$.

$\endgroup$
2
  • 2
    $\begingroup$ Good answer, but I suspect there is room for improvement. (For example, you always place the item to be weighed in the same pan, when it could go in any of them, with or without some accompanying weights.) $\endgroup$
    – fljx
    Feb 8 at 9:42
  • $\begingroup$ I had the same thought, but having the target weight in a different pan is equivalent to having an appropriate multiple of the target weight in the original pan. Since 469 factorizes into 7×67, you'll be hard-pressed to modify this setup into one that can accommodate an appropriate ratio. $\endgroup$ Feb 8 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.