Centrifuge solution

This is a solution to problem 24 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

The trick here is that the superposition of two solutions is another solution, provided, of course, that they do not overlap. Here, we can superpose a solution for 3 tubes (4, 8, 12) and one for 2 tubes (3, 9).

Now we ask, for what numbers of test tubes is there a solution? There are solutions for 0, 2, 3, 4, 5, and 6 tubes. Note that the complement of a solution is also a solution, so therefore the only numbers for which there is no solution is 1 and 11.

---

QuietLight: I'm not sure what you mean by "sides." The requirement is that the centrifuge be radially balanced, that is, that the sum of the vectors from the center to each test tube is 0. The vectors for the tubes at 4, 8, and 12 sum to 0, as do the vectors for 3 and 9. 0 + 0 = 0.

Putting the 5th test tube in the center is clearly cheating ;-)

(Note: I agree that the writeups that follow mine prove me wrong. For the sake of the references made in other writeups, I am keeping this as is)

I am sorry to say, but this is an incorrect solution. The organization of the previous test tubes is as follows:

          1
       2     12
     3         11
    4           10
     5         9
       6     8
          7

This leaves the 12 side weighing less than the 3/4 or 8/9 sides. Therefore, the centerfuge will rock out of orbit due to the force of the two heavier sides. As a result, it will vibrate its way across the labtable onto the floor. The only way to make 5 tubes fit is to put 4 in equally (3,6,9,12) and place the 5th one in the center, if the centerfuge can hold it.

Actually, the system is balanced even vertically, not just radially. (e.g. if you put the weights on a bicycle wheel and let it free, it won't move). The error is a common misconception of those who try to make perpetual motion machines. Just because there are more items on one side than on the other does not mean that the system is not balanced. An equilateral triangle will not move if mounted on a central pivot and placed vertically, regardless of the initial orientation.

If you have doubts, do some trigonometry to figure out the component forces exerted by the weights, or try it with a bicycle wheel.

Or, if you like, take a look at the Museum of Unworkable Devices (http://www.lhup.edu/~dsimanek/museum/unwork.htm).

Failing that, build a machine that is inherently unbalanced in any orientation, win the Nobel Prize, the adoration of millions of scantily clad women, and perhaps some self esteem (crucial to your subsequently destined profession as the second coming, being as you will have solved a vast chunk of humanity's problems).

The centrifuge problem states that a centrifuge with some arbitrary number of test tubes in it must be radially balanced — that is, its center of mass must be in the center of the centrifuge. An unbalanced, spinning centrifuge will shake and "walk" across a desk like an unbalanced washing machine, and the vibrations caused by the unbalanced load will damage the spinning mechanism. So it is critical to balance it as well as possible, especially in very high-speed applications.

The specific problem given in the node Hard interview questions states that the centrifuge has 12 evenly spaced slots for test tubes, and that all the test tubes have equal mass. The solutions for 0, 2, 3, 4, and 6 tubes are trivial since they divide evenly into 12 and can therefore be evenly spaced. Likewise the solutions for 8, 9, 10, and 12 are exactly the same if you consider evenly spacing 0, 2, 3, or 4 empty slots rather than full slots.

Clearly the 1 and 11 test tube cases are not possible because there is nothing left with which to balance one and only one full or empty slot. This is also obvious and trivial.

However, the 5 and 7 test tube cases are nontrivial. 5 and 7 do not divide evenly into 12 and therefore cannot be evenly spaced around the centrifuge. Here is one possible arrangement which might work:

          C
       B     1
     A         2
    9           3
     8         4
       7     5
          6

One commonly given proof that this arrangement is valid is that it is the superposition of two other valid arrangements, the solutions for 2 and 3. But this doesn't tell you anything if you don't understand superposition.

We can check to see if it is valid by calculating its center of mass. We can do this with basic trigonometry. If this arrangement is balanced both left to right and top to bottom, then it is balanced. Trigonometry allows us to find the horizontal and vertical components of each item's mass with respect to the center by drawing triangles. The hypotenuse of the triangle is the actual mass of the test tube and the horizontal and vertical legs represent the horizontal and vertical components of its mass.

First we see that the mass at C (slot 12) has only a vertical component. The masses at 3 and 9 likewise have only a horizontal component. So we only need triangles to find the horizontal and vertical components of 4 and 8. Recall the trigonometric identities:

        opposite                 adjacent
sinθ = ----------        cosθ = ----------
       hypotenuse               hypotenuse

Each slot represents 30° (360°/12). For convenience, let us assume the mass of each test tube is one (zero being an easier but far less interesting case). This sets the hypotenuse equal to 1, which therefore drops out of the equations, leaving us with:

Vertical components:     Horizontal components:
sin(-30)  = -1/2         cos(-30)  =  √3/2
sin(-150) = -1/2         cos(-150) = -√3/2

Now we add up all the vertical and horizontal components of the masses, defining up and right as positive.

Vertical:
C + 9 + 3 + 8      + 4 = 
1 + 0 + 0 + (-1/2) + (-1/2) = 0 Balance!

Horizontal:
C + 9    + 3 + 8       + 4 = 
0 + (-1) + 1 + (-√3/2) + √3/2 = 0 Balance!

Therefore this solution is valid. The 7 test tube case is the same, just with the empty and full slots reversed.

In fact, this is only one valid solution to the problem. By running the math the same way, we see that any combination of any solution for 2 test tubes and 3 test tubes will work, so long as you don't try to put two test tubes in the same slot. For example, the case C, 4, 8, B, 5, although it looks unbalanced at first glance, still works:

Vertical:
C + 4      + 8      + B    + 5 = 
1 + (-1/2) + (-1/2) + √3/2 + (-√3/2) = 0 Balance!

Horizontal:
C + 4    + 8       + B      + 5 = 
0 + √3/2 + (-√3/2) + (-1/2) + 1/2 = 0 Balance!

Really this is just the same case rotated 120 degrees. C, 4, 8, 1, 7 is the mirror image of that and also works. Superposition would have told us this immediately.

Superposition
As mentioned earlier, the 5 test tube case is just the 2 and 3 test tube cases put together. Consider the cases separately. A valid 3 test tube case balances, so the center of mass doesn't need to be considered when looking at the 2 test tube case. Likewise a valid 2 test tube case balances, so its center of mass doesn't need to be considered when looking at the 3 test tube case. Each case completely drops out of the analysis of the problem because its center of mass is at the center, exactly where we need it to be.

Essentially, we are saying that two arrangements that each equal zero separately also equal zero when considered together.