The broken weight problem: solutions and further exploration

First of all, let me say to all my readers how fantastic it felt to post a puzzle, after not posting anything for two months, and get eighteen thoughtful, insightful comments in just three days; it’s every blogger’s dream. You all are fantastic and make this a lot of fun — thanks for reading!

I thought I’d take a post just to summarize some of the responses and solutions to the broken weight problem. As many commenters realized, the solution is that the weights are of sizes 1, 3, 9, and 27. Hmm, powers of three… coincidence? Of course not!

As several commenters noted, something involving base three readily presents itself if we realize that there are three possibilities for each weight: it can be on the left of the balance scale, on the right, or not on the scale at all. Since one side of the scale corresponds to adding the weight and the other side to subtracting, we are essentially writing numbers in base three, but using the digits -1, 0, and 1 instead of the usual 0, 1, 2. For example, 25 can be written as 10(-1)1, that is, 1 \cdot 27 + 0 \cdot 9 - 1 \cdot 3 + 1 \cdot 1 (if we were really going to use this system we’d want to come up with a better symbol for -1). In fact, this is known as balanced ternary, and it is a fact (as proved by a few commenters) that n digits of balanced ternary allow us to uniquely represent every integer between \pm \frac{3^n - 1}{2}. With four digits (as in the problem) we can uniquely represent every integer between -40 and 40. There was a bit of confusion in the comments about being able to represent some integers in more than one way, but I think if you try it out you will find that this is not the case.

From this problem (generalizing it to arbitrary numbers of weights), we can see that

\displaystyle 1 + 3 + \dots + 3^{n-1} = \frac{3^n - 1}{2}.

JM noted that this generalizes to

\displaystyle 1 + b + b^2 + \dots + b^{n-1} = \frac{b^n - 1}{b - 1}

and wondered whether this has anything to do with solving the problem, or with problems like it. Indeed it does; here’s one for you: suppose you are tasked with designing a set of weights. The weights should make it possible to weigh as many different integer weights as possible, without leaving any out, just like the weights 1, 3, 9, 27 make it possible to weigh every integer weight up to 40 without leaving any out. The one difference is that you want to have two identical copies of each weight. What is the best you can do?

I’ve left the problem slightly vague on purpose, but I hope you will have fun solving it and figuring out what it has to do with JM’s observation! Can you come up with other interesting generalizations of the problem?

Finally, Sam Shah posted a link to a description of his experience using the problem in a real-life problem-solving session.

About these ads
This entry was posted in arithmetic, challenges, number theory, solutions and tagged , , , , . Bookmark the permalink.

6 Responses to The broken weight problem: solutions and further exploration

  1. JLR says:

    Ooh, very nice! Fairly straightforward, but much less intuitive.

  2. Fergal Daly says:

    I’ve been thinking of it in terms of every-day ternary numbers offset by a constant

    So

    a+b*3+c*9+d*27

    where a, b, c and d can be -1, 0 or 1 is just

    e+f*3+g*9+h*27 – (1+3+9+27)

    where e = a + 1, f = b + 1, etc and e, f, g, h are all 0, 1 or 2, just like everyday ternary.

    So every arrangement of stones corresponds to a 4-digit ternary number and the weight it balances is equal to that ternary number – 40. If we allow a 5th stone, we just look at 5-digit ternary numbers and subtract 121 (1+3+9+27+81).

    Since every number from 0-80 has a unique ternary representation, every number from -40 to +40 has a unique rep using -1, 0, 1.

    E.g. to get the rep for 7, add 40 to get 47 which is 2*1+0*3+2*9+1*27 and now reduce all the digits by 1 to get 1*1-1*3+1*9+0*27, which is indeed 7.

    BTW the number you add or subtract is written 1111 in ternary which makes perfect sense as subtracting that changes each digit by 1. Traditionally we carry 1 in order to keep the digits positive but in this case we want to use -1, 0 and 1.

    I think this way of looking at it helps a lot with the generalisation to 2 (or N) copies of each stone.

  3. JM says:

    Nice! So if the rule is that you can only use weights that are powers of an odd number n, you need to make (n-1)/2 copies of each increment to measure all integer weights. If n is even, then you would need n/2 copies, and there would be two ways to get to that middle number.

  4. Tom says:

    The idea of b is that it is the number of locations you can have. So 2 on each side and not there at all. Thus:

    1+5+25 (ie. 2 x 1 lb, 2 x 5 lb, 2 x 25 lb) six weights total

    two of each.
    3 = 5 / 1,1
    13 = 25 / 5,5,1,1 for example

  5. Michael says:

    Hi,

    Your blog caught my eye with the proof of irrationality of Pi with an integral — really neat. Haven’t really read math blogs before, they’re a cool treat.

    In relation to this problem, I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?

    Cheers,

    Michael

    • Brent says:

      Hi Michael,

      Thanks, glad you enjoyed reading the proof of irrationality of pi! Your question about change is a really interesting one, I think I will post it as a challenge problem!

Comments are closed.