Ternary Numeral System

First some wiki links to get familiar with the base 3 numerical system -

Ternary numeral System : base 3 system as most of the people imagine it to be

Balanced ternary : an interesting form with several advantages.

I will discuss here, the "two" problems that got me interested in "ternary" numeral system -

note : now that I have mentioned ternary, these problems are mere exercises.

Problem 1 :

"""

A 40 kg stone breaks into 4 pieces. Determine the weight of those 4 pieces such that using them and a "2-pan" balance you can measure all the weights from 1kg to 40kg.

"""

Solution : This can be easily solved by playing around a bit. Here's one line of thought -

It's a good guess to start with that exactly 1 piece must weigh 1 kg. And then to measure 2kg, lets take a piece weighing 3kg. So till now we can measure weights from 1 to 4. What should be the 3rd piece. We can check one by one weights from 5 onwards, which is the weight that gives longest sequence of weights starting from 5. We can easily see that if we take the 3rd piece to be 9kg, then we can measure all the weights from 1 to 13. So the 4th piece is 40 - 13 = 27kg.

And now it can be easily verified 1,3,9,27 solves the problem.

Generalizing the above solution suggests that powers of 3 have some "nice property" which can be used in this "2-pan" balance problem. Let's see why is it so.

Some formalism will be useful here -

set the 4 pieces be x1,x2,x3,x4. The constraints are

a) x1 + x2 + x3 + x4 = 40

b) a1*x1 + a2*x3 + a3*x3 + a4*x4 gives all the numbers from 1 to 40 with ai's in {-1,0,1}

it is the second constraint that suggests base 3 system here. The coefficients are 3 consecutive numbers, -1, 0 and 1. Using euclidean division we can prove that any number n can be written as a0 + a1*3 + a2*3^2 ... where ai is in {r-1, r, r + 1} for some integer r. For r = 1 we get the standard base 3 representation and with r = 0 we get the balanced ternary system.

So if we take 4 weights {1,3,9,27} using them and a balanced ternary system we can represent all the numbers from -40 to +40. And as it should be clear that using a 2-pan balance is same balanced ternary system, we know that we can measure all the weights from 1 to 40.

Problem 2 :

"""

You have eight balls all of the same size. Seven of them weigh the same, and one

of them weighs slightly more. How can you find the ball that is heavier by using a 2-pan balance and only two weighings?

"""

Solution : Thinking for a while gives the following heuristic -

Take two groups of 3 balls say A,B. Weigh them, if A = B then the heavy ball is in remaining 2 balls which can be found in another weighing. Else, say A > B. Now, we need to find the heavy ball from a group of 3 balls using 1 weighing. Even this is quite easy as you can pick 2 balls, compare them and if they are equal the one that is left is the answer else the heavier one is.

Let's Generalize!

What is the minimum number of weighings that is required for identifying a the heavy balls from N balls.

Say f(N) is the solution.

Playing around a bit gives this values for f

f(2) = f(3) = 1

f(4) = f(5) = f(6) = f(7) = f(8) = f(9) = 2

If you observe carefully, then f(N) is the number of "trits" ( :P ) in N. (N > 1)

which is actually clear if you see the recurrence relation

f(N) = f(N/3) where N/3 = floor(N/3)

and f(3) = 1

hence f(N) = floor( log3(N) + 1) = number of trits in N