7
$\begingroup$

Would I be wrong to assume that the solution to this problem:

What is the length of the shortest pipe, of internal radius 50mm, that can fully contain 21 balls of radii 30mm, 31mm, ..., 50mm?

...involves stacking the balls, from largest to smallest, with each ball resting against the last on alternate sides of the pipe? Like so:

Most efficient packing arrangement?

Thus reducing this to a relatively straightforward geometry problem. The reason I ask is because my solution to this arrangement -- calculated in two different ways -- doesn't pass; so I guess there's some kind of subtlety that I'm missing (i.e., making false assumptions!).

  • 0
    If your solution does not pass, what is the actual answer quoted?2013-12-16

3 Answers 3

5

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.

  • 0
    1. There is no need to check the "(small, small) do not fit in the tube" because 2*30 + 2*31 > 100. 2. It turns out that the biggest + smallest combination is not the o$p$timal.2013-12-24
3

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:-

  1. “Putting two smallest spheres adjacent to each other will give a largest gain in X.” ----(*)

  2. “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.]

1

This is not an answer but is a nice way to see it:

Let's call our ball "cities"

And the distances they add

To the pipe we have,

when stacked, "paths"

What do we have?

 

A traveling salesman! For this specific problem, maybe we can optimize the search, but modern algorithms are already capable of solving it.

  • 1
    Questions of this type is mostly answer-oriented. At the most, it is looking for how the objects are arranged. Keeping the largest spheres apart and keeping the smallest spheres together are direct deductions from the decreasing nature of F(T). The others are educated guesses. Of course, a formal proof is undeniably the best. Looking forward for viewing your work.2013-12-27