Project Euler Question 222
I have spent some time in trying to "prove" the '50, 30, 49, 31....' configuration is correct. There may be some points I missed.
Define $H(x) = √[(100 – x)^2 – x^2] = … = 10 √(100 – 2x)$, which is therefore a decreasing function. Let $K(x) = H(50 – x) = 10√[2x]$ . It is therefore an increasing function.
Let the 21 spheres be labeled as $S_{50}, S_{49}, …, S_{30}$ where $S_{50}$ is the one whose radius = $R_{50} = 50$. The rest are similarly defined. The spheres are to be placed inside a pipe of radius $= 50$ in such a way that they should occupy the shortest length ($L$) of the pipe.
The sizes of the spheres forbid that no any two can fit in the pipe side by side.
Strategy:- Place the largest sphere ($S_{50}$ in this case) first, and followed by $S_k$ where $k = 49, 48, … , 30$.
Length required $= 50 + √[(50 + k)^2 – (100 – 50 – k)^2] + k$ ; for $k = 49, 48, … , 30$
$= 50 + k + √[(100 – (50 – k))^2 – (50 – k)^2]$
$= 50 + k + 10√[100 – 2(50 – k)]$
$= 50 + k + 10√[2k]$
Minimum length occupied $= 157.4596669$ occurred when $k = 30$.
Conclusion:- Placing the smallest sphere on top of the largest will give a better usage of the pipe.
After the above, the problem is reduced to one that has $19$ spheres, and they’re $S_k$; where $k = 31, 32, …, 49$.* The strategy is then repeated until we have only one sphere (which is $S_{40}$) left.
Stacking one sphere on the other results in a small gain in length, $X$, which is given by:- $X = T – √[T^2 – (T – 100)^2]$; where $T =$ the sum of radii of the two spheres.
{The derivation of $X$ can be found in Problem here.}
We will use $X_{v,u}$ to denote the length gained by stacking $S_{v}$ on top of $S_{u}$.
- Hence, after stage-1, the problem is now reduced to “letting the 19 spheres ($S_{49}, S_{48}, …, S_{31}$) to fit the pipe; with the $S_{49}$ being the largest but with the bottom part being flattened". The process is then repeated until .... Then L is given by:-
$L = (S_{50}+S_{30} combination) + (S_{49}+S_{31} – X_{49,31}) + … + (S_{41}+S_{39} – X_{39,41}) +2*40 – X_{40,41}$
If such arrangement is accepted as the most optimal, then L can be found alternately as:- $L = R_{50} + (R_{50} + R_{30} – X_{30,50}) + (R_{30} + R_{49} – X_{49,30}) + … + (R_{41} + R_{39} – X_{41,39}) + (R_{39} + R_{40} – X_{39,40}) + R_{40}$
= $2∑$$R_k$ – sum of the 20 extra lengths gained by stacking the spheres
The former sum is an AP but the latter, unfortunately, is rather irregular.
EDIT: The last comment (about the sum is irregular) that I made (few days ago) should now be changed for the following reason:-
Let $X_{v,u} = T_{v,u} – √[T_{v,u}^2 – (T – 100)^2]$; where $T_{v,u} =$ (the sum of radii of $S_v$ and $S_u) = v + u$.
Then, $X_{v,u} = … = (v + u) – √[200(v + u) – 100^2]$
Note that:- $X_{30,50} = X_{31,49} = … = X_{39,41} = {80 – √[200(80) – 100^2]} = 80 – √6000$
Similarly, $X_{49,30} = X_{48,31} = … = X_{40,39} = {79 – √[200(79) – 100^2]} = 79 – √5800$
Sum of the $20$ extra lengths gained by stacking the spheres $= X_{30,50} + X_{49,30} + X_{31,49} + X_{48,31} + X_{32,48} + … + X_{38,42} + X_{41,38} + X_{39,41} + X_{40,39}$
= $[X_{30,50} + X_{31,49} + X_{32,48} + … + X_{38,42} + X_{39,41}] +[X_{49,30} + X_{48,31} + … + X_{41,38} + X_{40,39}]$
$= 10 × [80 – √6000] + 10 × [79 – √5800]$
$= 53.826xxx$
$L = 1680 - 53.826xxx = 1626.173xxx$
The above is only for the calculation of the length occupied by the $S_{50} + S_{30} + S_{49} + ... $ configuration. Such configuration may not the optimal setup. I am working on other possible arrangement.
In connection to my previous post, I suggest the following as a better configuration.
Continuing from the previous post, we have
$X_{v,u} =$ Extra length gained when stacking $S_v$ onto $S_u$
$= (T) – √[200(T) – 100^2]$; where $T = v + u$ = the sum of the two radii
$L = 2∑R_k–∑X_i$ (where $R_k$ is the radius of the $k$-th sphere and $i = 1, 2, …,20$.)
Then, $Min(L) = Min(2∑R_k –∑X_i)$ $= 2∑R_k– Max(∑X_i ) = 2∑R_k– Y$ (say)
Thus, in order to find Min(L), it is sufficient to find the largest of Y’s from different configurations.
Before we go on, we diverse a bit to point out that $F(T) = T – √(200T–100^2)$ is a decreasing function in the interval $[61, 99]$.
[The proof, which involves the showing of $F’(T) < 0$, is rather strict forward and is omitted.]
The decreasing function provides the following hints for the best stacking method:-
“Putting two smallest spheres adjacent to each other will give a largest gain in X.” ----(*)
“Putting two largest spheres adjacent to each other will give a shortest gain in X.” ----(#)
Let’s first take a look at the simplified situation of having only 3 spheres ($S_{30}$, $S_{49}$, and $S_{50}$)
We need to consider the following 3 cases only:-
The largest in the middle-----$Y(S_{30}, S_{50}, S_{49}) = 2.54538371$
The medium in the middle---$Y(S_{30}, S_{49}, S_{50}) = 2.8473196$
The smallest in the middle---$Y(S_{50}, S_{30}, S_{49}) = 5.38260202$
From this, our observation is
“Putting the smallest between the two largest will get a better gain in length.” ----(@)
This can also be verified mathematically as:-
$Y(S_{50}, S_{30}, S_{49}) – Y$(some other combinations)
$= Y(S_{50}, S_{30}, S_{49}) – Y(S_{30}, S_{49}, S_{50})$; [as an example]
$= (X_{49,30}+ X_{30,50}) – [X_{50,49} + X_{49,30}]$
$= X_{30,50} – X_{50,49}$
$= [80–√[200(80)–100^2] – [99–√[200(99)–100^2]$
$ > 0$ (since $F(T)$ is a decreasing function.)
Next, consider the case of having only 4 spheres (2 largest ($S_{50}$ & $S_{49})$ + 2 smallest $(S_{30}$ & $S_{31})$.
Case-1. Placing the largest two adjacent to each other
----$Y(S_{30} + S_{49} + S_{50} + S_{31}) = … = 5.10724084 =$ length gained is too small
----$Y(S_{50} + S_{49} + S_{31} + S_{30}) = … = 16.6412261$
Case-2. Pair up (One small + one large)
--- $Y(S_{31} + S_{49} + S_{30} + S_{50}) = … = 7.92293509 = $length gained is too small
--- $Y(S_{30} + S_{49} + S_{50} + S_{31}) = … =$ length gained is too small (as case1-(i))
Case-3. Placing the smallest two adjacent to each other
--- $Y(S_{50} + S_{31} + S_{30} + S_{49}) = … = 19.1980326$
--- $Y(S_{50} + S_{30} + S_{31} + S_{49}) = … = 19.176509$
--- $Y(S_{50} + S_{49} + S_{31} + S_{30}) = … = 16.xxxxx$ (as case1-(ii))
This shows that the $S_{50} + S_{31} + S_{30} + S_{49}$ combination has a better usage of the pipe. In fact, all these figures further verified the correctness of (*), (#) and also (@). And they also give us another hint:-
“The largest two spheres should be placed at the far ends (one in each end) of the pipe.” ----(%)
Summing these up, I propose the following configuration:-
$(S_{50}+S_{48}+ … +S_{40}+S_{38}+S_{36}+ … +S_{32})+S_{30}+[S_{31}+S_{33}+ … +S_{47}+S_{49}]$
The corresponding extra length gained $= 89.06688385$
$Min(L) = 1590.933116$, [a figure far less than the $S_{50}+S_{30}+S_{49}+S_{31}+ ...$ configuration.]