On today's TopCoder Single-Round Match, the following question was posed (the post-contest write-up hasn't arrived yet, and their explanations often leave much to be desired anyway, so I thought I'd ask here):
Given a maximum of 8 marbles and their radii, how would you put them next to each other on a line so that the distance between the lowest point on the leftmost marble and the lowest point on the rightmost marble is as small as possible?
8! is small enough number for brute forcing, so we can certainly try all permutations. However, could someone explain to me, preferably in diagrams, how to calculate that distance value given a configuration?
Also, any kind of background information would be appreciated.
If I understand well, the centers of the marbles are on the line.
In that case, we can fix a coordinate system such that the $x$-axis is the line, and the center $C_1$ of the first marble is the origin. Then, its lowest point is $P=(0,-r_1)$. Calculate the coordinates of the centers of the next circles: $$C_2=(r_1+r_2,0),\ C_3=(r_1+2r_2+r_3,0),\ \dots,\ \\C_n=(r_1+2r_2+\ldots+2r_{n-1}+r_n,\ 0)$$ The lowest point of the last circle is $Q=(r_1+2r_2+..+2r_{n-1}+r_n,-r_n)$. Now we can use the Pythagorean theorem to calculate the distance $PQ$: $$PQ^2=(r_1+2r_2+..+2r_{n-1}+r_n)^2+(r_1-r_n)^2= \\=\left(2\sum_{k=1}^n r_k-(r_1+r_n)\right)^2+(r_1-r_n)^2\,.$$ It follows that the distance is independent of the order of the intermediate marbles, only the first and the last one counts. Hopefully from here you can calculate the minimum of this expression.