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?
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 JagyCommented May 15, 2017 at 1:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered May 15, 2017 at 1:21
$\begingroup$
$\endgroup$
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$.
