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:
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:
sinθ = ---------- cosθ = ----------
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.
C + 9 + 3 + 8 + 4 =
1 + 0 + 0 + (-1/2) + (-1/2) = 0 Balance!
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:
C + 4 + 8 + B + 5 =
1 + (-1/2) + (-1/2) + √3/2 + (-√3/2) = 0 Balance!
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.
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.