2
$\begingroup$

Say you had a scale, with two weights of two different values used to balance it. Is there any way to determine if two given weights could be used to weigh any arbitrary object? For example, say the weights are 5 and 12 ounces. Is there any way to prove that these weights could be added to both sides of the scale in any possible combination so that an equilibrium could be reached if an object of any weight was being weighed?

$\endgroup$
1
  • $\begingroup$ the gcd is one. meaning, if you have an unlimited supply of weights, you can correctly weigh any number of ounces. $\endgroup$
    – Will Jagy
    May 15 '17 at 1:19
1
$\begingroup$

Assuming you have lots of each kind of weight, you can weigh any multiple of the greatest common divisor of the weights. Here that is $1$ ounce. Bezout's identity tells you so.

$\endgroup$
0
$\begingroup$

Notice that $5 \times 5 - 12 \times 2 = 1$.

Therefore, if you have an object of $n$ ounce, you can always put $2n$ objects of $12$ ounce on the same side, and $5n$ objects of $5$ ounce on the other side: $$n+(2n)(12) = (5n)(25)$$

This is possible because $5$ and $12$ are co-prime.


In general, Bézout's identity states that, for integers $a$ and $b$ with GCD $g$, it is possible only for multiples of $g$. In the previous case, $5$ and $12$ are co-prime, so their GCD $g$ is $1$, so it is possible for any integer, since any integer is a multiple of $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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