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!).

  • 3
    I also believe you'd up with a more efficient solution just by alternating 50,30,49,31,48,32, etc.2012-01-10
  • 0
    That makes sense. Perhaps, then, the balls should be stacked as 50, 30, 49, 31, 48, 32,...2012-01-10
  • 0
    @JacobSchlather You beat me to it ;)2012-01-10
  • 0
    ...That arrangement didn't work either :P2012-01-10
  • 1
    I would have thought it likely, since this is a Project Euler problem, that you'd have to search through the permutations in some way to find the optimal one.2012-01-10
  • 0
    It seems kind of lame to have a math stackexchange question devoted to a specific project euler puzzle.2012-01-10
  • 2
    The point of the problem is to determine the most efficient packing order. One can define that unambiguously, then do the computation. It is not largest to smallest2012-01-10
  • 2
    Here is a meta thread about Project Euler question discussion in math.stackexchange ... http://meta.math.stackexchange.com/questions/1090/re-project-euler-questions2012-01-10
  • 0
    @TonyK: What was going through my mind and what I wrote were two different things. I think I'll delete my comment since more helpful ones have emerged since.2012-01-10
  • 0
    If your solution does not pass, what is the actual answer quoted?2013-12-16

3 Answers 3

4

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
    Would not be much simpler just to consider the two balls case (starting with a "big" ball say)? If you start with the biggest then the solution is clearly (biggest,smallest). Then you just have to check that pairs of (small,small) do not fit in the tube so you will always alternate (big,small,big,...). The overall minimization over pairs is obtained putting them in decreasing order.2013-12-24
  • 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 optimal.2013-12-24
2

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

0

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.

  • 0
    Thanks for accepting the post as "nice way to see it". The previous post is definitely not the answer because it is just showing how the '50+30+49+31+...' configuration can be summed. I am now proposing another configuration in my second post.2013-12-26
  • 0
    @Mick I would say that your solution is the greedy solution of the problem (locally optimized), but it does not guarantees the big picture is the best one. Your post mostly has heuristic-motivated, but formally unjustified, observations. I would like to see them formalized with a proof, and I will see if I can do that (If you do it it would be great also). But I will also go from the other side, by solving the TSP I proposed and seeing if I get a better configuration. Cheers for the good work though!2013-12-26
  • 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