Cutting a cuboid to fit in a hemisphere

Solution 1:

I would propose a possible solution that is probably very far from the optimal one, but has the advantage of being quite simple and with a relatively regular pattern (the optimal solution for this problem could be very complex and highly irregular). The idea is to break the noodle package into small cubes and to arrange them in successive layers to obtain a hemispherical-like shape. Importantly, in this solution, I assumed that multiple pieces can be appropriately placed (e.g, stacked or side by side) in order to be cut together with a single cutting plane, with no limitations to the number of pieces simultaneously cut in this way. Therefore, with relation to the issue raised in the comments, this solution follows the "two breaks" assumption (for example, making $2$ cuts to get four $1\times 1\times \frac 12$ pieces counts as $2$ breaks, even if the second cut divides two different pieces).

$\textbf{General rule for the cut sequence}$. Let us start by dividing our noodles in four $1\times 1\times \frac 12$ pieces with two perpendicular cuts, and then in sixteen $\frac 12\times \frac 12\times \frac 12$ cubic pieces with two other perpendicular cuts. Under the assumption above, such cuts can be easily made by stacking the pieces or placing them side by side. By similar considerations, after these four initial cuts, we can reduce by a factor $1/2$ the side of all cubes - thus multiplying their number by $2^3$ - by three additional perpendicular cuts that divide the stacked cubes (or parallelepipeds, after the first and before the third of these additional cuts) in half along the three axes. This last process can be iterated, with successive groups of similar triple cuts. So, generalizing, if $z$ is the number of these groups of triple cuts, by $4+3z$ cuts we can obtain $2^{4+3z}$ cubes, each with side $h=1/2^{1+z}$ and volume $1/2^{3+3z}$.

$\textbf{Bounds for the layers}$. Once we defined the method to cut our noodle package in cubes, we can begin to arrange our cubes to create a hemispheric-like shape. In this solution, by simplicity, the shape will be flipped in comparison with the natural position of the bowl, i.e. we will try to fill a hemispheric cavity resting on its flat face. We will do it by overlapping successive layers of cubes containing a decreasing number of cubes as we procede from bottom to top of our arrangement. However, the whole procedure can be easily reversed if we want a more realistic method to fill the bowl.

Looking at our hemispheric cavity from the top, each layer is formed by cubes arranged in a way to cover a circular area with decreasing radius as we move towards the higher layers. Starting from the bottom layer, the cubes have to be positioned within a circle whose radius is slightly lower than $1$. In fact, since the cubes have height $h$, they necessarily must be placed within the circle obtained by cutting the ideal hemispheric cavity with a plane parallel to its flat face at a distance $h$ from it. The radius of this circle is $\sqrt{1-h^2}$. By similar considerations, the cubes of the second layer have to be placed within the circle obtained by cutting the hemispheric cavity with a plane parallel to its flat face at a distance $2h$ from it. The radius of this second circle is $\sqrt{1-(2h)^2}$. Extending this to the successive layers, we get that, in general, the cubes of the $j^{th}$ layer have to be placed within a circle whose radius is

$$r_{j,h}=\sqrt{1-(jh)^2}$$

Note that the maximal number of layers is not $1/h$, since there is necessarily a distance between the upper face of the highest layer and the apex of the hemisphere. Even in the best possible scenario that minimizes this distance (i.e., that where the arrangement of the cubes has a single central cube in the highest layer that touches the hemisphere with its four upper vertices), the block of layers has a total height of $\sqrt{1-h^2/2}$. Since this is only a theoretical best scenario, for any given $h$ the maximal number of layers that can be placed within the hemispheric cavity is actually

$$j_{max,h}=\left\lfloor \frac{ \sqrt{1-h^2/2}}{h} \right\rfloor =\left\lfloor \sqrt{\frac{1}{h^2}-\frac 12} \right\rfloor $$

For the cases that we are going to analyze, in which $h=1/2^{1+z}$, the expression for the value of $j_{max,h}$ can be simplified. In fact, we can rewrite the RHS as $\lfloor \sqrt{2^{2+2z}-1/2}\rfloor$. It is not difficult to note that the quantity $2^{1+z}-\sqrt{2^{2+2z}-1/2}$ is decreasing in the range of $z\geq 0$, starting from a value of $2\sqrt{7/2}\approx0.129$ for $z=0$. Since $2^{1+z}$ is integer, then $\lfloor \sqrt{2^{2+2z}-1/2}\rfloor =2^{1+z}-1$ and

$$j_{max,h}=\frac{1}{h}-1$$

$\textbf{Building the layers}$. Now let us try to build the single layers. In each of them, within the corresponding circle with radius $r_j$, we can firstly place the cubes side by side to form the largest possible square contained in the circle. The best possible case is a square with side $r_j \sqrt{2}$ inscribed in the circle. However, since we have to cover this square using cubes with side $h$, the largest possible square contained in a circle with radius $r_j$ actually has a side given by

$$s_{j,h}=h\left\lfloor \frac{r_{j,h} \sqrt{2}}{h} \right\rfloor$$

The figure below shows an example for the bottom layer in the case $h=1/4$, as seen from the top. The cubes in this layer have to be placed within the circle with radius $r_{1,\,1/4}=\sqrt{1-(1/4)^2}$ $=\sqrt{15}/4\approx 0.968$ (showed in blue), slightly smaller than the circle with radius $1$ that forms the flat face of the hemisphere (dotted circle). The inscribed square (dotted square) has side $=\sqrt{30}/4\approx 1.369$, but since we have to form the square using cubes with side $1/4$ we can get a smaller one, with side $s_{1,\,1/4 }=1/4 \cdot \left\lfloor \frac{ \sqrt{30}/4 }{1/4} \right\rfloor=1.25$, covered by a $5 \times 5$ arrangement of the cubes.

In each layer, after we have formed the central square, we can try to fill the four remaining circular segment regions. To do this, we can begin by placing four row of cubes, each adjacent to one side of the square. Since the cubes have size $h$, the maximal width of these rows is not $s_{j,h}$, but $2\sqrt{r_{j,h}^2-(s_{j,h}/2+h)^2}$. So, on each side of our square, we can place a first row of $\lfloor 2\sqrt{r_{j,h}^2-(s_{j,h}/2+h)^2} /h \rfloor$ cubes. Repeating the process, we can place, externally to each of these rows, a second row of $\lfloor 2\sqrt{r_{j,h}^2-(s_{j,h}/2+2h)^2} /h \rfloor$ cubes, a third row of $\lfloor 2\sqrt{r_{j,h}^2-(s_{j,h}/2+3h)^2} /h \rfloor$ cubes, and so on. Generalizing, the $k^{th}$ group of four rows includes $4\lfloor 2\sqrt{r_{j,h}^2-(s_{j,h}/2+kh)^2} /h \rfloor$ cubes.

As already noted for the maximal number of layers, within any layer the maximal numbers of rows filling each of the circular segments is not $r_{j,h}/h$, since there is necessarily a distance between the external face of the most external row and the circle. Even in the best possible scenario that minimizes this distance (i.e., that where there is a single central cube in the more external row that touches the hemisphere with its two upper external vertices), the block of rows has a total width of $\sqrt{r_{j,h}-h^2/4}-s_{j,h}/2$. Again this is only a theoretical best scenario, because for any given $h$ the maximal number of rows that can be placed within the circle corresponding to the $j^{th}$ layer is

$$k_{max,j,h}=\left\lfloor \frac{ {\sqrt{r_{j,h}^2-h^2/4}}-s_{j,h}/2}{h} \right\rfloor $$

In the same example above, for the bottom layer in the case $h=1/4$, we would have

$$k_{max,1,\,1/4}=\left\lfloor \frac{ {\sqrt{15/16-(1/4)^2/4}-1.25/2}}{1/4} \right\rfloor =\left\lfloor \frac{\sqrt{59}/{8}-5/8}{1/4} \right\rfloor =1 $$

indicating that only a single row for each of the four circular segments can be added to the central square. These four rows contains a total of $4\lfloor 2\sqrt{15/16-(1.25/2+0.25)^2} /0.25 \rfloor=12$ cubes, i.e. three cubes each. Summing these cubes to those of the central square, we get a total of $25+12=37$ cubes. Accordingly, the figure below shows the completed bottom layer for this example, as seen from the top:

$\textbf{Total count of cubes}$. Collecting all these results, we get that the number of cubes with side $h$ that can be arranged within the $j^{th}$ layer is

$$T_{j,h}=\left( \frac{s_{j,h}}{h}\right)^2 + 4\sum_{k=1}^{k_{max,j,h})} \left\lfloor \frac{2 \sqrt{r_{j,h}^2-(s_{j,h}/2+k h)^2}}{h}\right\rfloor $$

where the first term of the RHS counts the cubes in the central square, and the second term counts those in the rows filling the four circular segments. The total number $T$ of cubes, summed across all layers, is then

$$T_h=\sum_{j=1}^{j_{max,h}} T_{j,h}$$

Using the formulas above, we can now determine the largest value of $h$ (cube side) and then the smallest value of $z$ (groups of additional triple cuts after the forst four cuts) that allows to place all resulting $2^{4+3z}$ cubes within the hemispheric cavity, i.e. satisfying $T\geq 2^{4+3z}$.

$\textbf{The case z=2}$. For example, let us try with $z=2$ additional triple cuts. By these cuts, we obtain $2^{10}=1024$ cubes with side $h=1/8$ and volume $1/512$. In this case our arrangement will have $j_{max,1/8}=1/(1/8)-1 =7$ layers. Starting from the bottom layer, we have $r_{1,1/8}=\sqrt{63}/8 \approx 0.992$ and the inscribed square has side $\sqrt{126}/8 \approx 1.403$, whereas the central square has side $$s_{1,1/8}=1/8\lfloor \sqrt{1-1/8^2} \sqrt{2}/(1/8) \rfloor=11/8=1.375$$ and is covered by $11\times 11$ cubes. The maximal number of rows in each circular segment is

$$k_{max,1,\,1/8}=\left\lfloor \frac{ {\sqrt{63/64-(1/8)^2/4}-11/8/2}}{1/8} \right\rfloor =\left\lfloor \frac{\sqrt{251}/{16}-11/16}{1/8} \right\rfloor =2 $$

so we have

$$T_{1,1/8}=\left( \frac{11/8}{1/8}\right)^2 + 4\sum_{k=1}^{2} \left\lfloor \frac{2 \sqrt{63/64-(11/16+k/8)^2}}{1/8}\right\rfloor =\\ 121+36+20=177 $$

as confirmed here. In other words, in each circular segment region we can add a first row of $9$ cubes and a second row of $5$ cubes. The figure below shows the resulting bottom layer in the case $h=1/8$:

For the successive layers, using the formulas above it can be shown that $k_{max,j,1/8}$ is equal to $2$ for $1\leq j\leq 5$, and to $1$ for $6\leq j\leq 7$, as confirmed by WA here. Following the same method as above and making the appropriate substitutions, we get $T_{2,1/8}=160$, $T_{3,1/8}=148$, $T_{4,1/8}=129$, $T_{5,1/8}=104$, $T_{6,1/8}=69$, and $T_{7,1/8}=37$, as shown here and here. This leads to a total number of cubes given by $T_{1/8}=824$, corresponding to $80.5\%$ of the total set of $1024$ cubes. Since we cannot place all cubes in the hemispheric cavity, cutting our noodle package in cubes of side $1/8$ is therefore not sufficient to put it entirely in the bowl using this arrangement.

$\textbf{The case z=3}$. Let us try with $z=3$. By these cuts, we obtain $2^{13}=8192$ cubes with side $h=1/16$ and volume $1/4096$. In this case our arrangement will have $j_{max,1/16}=1/(1/16)-1=15$ layers. Proceeding as above it can be shown that $k_{max,j,1/16}$ is equal to $4$ for $1\leq j\leq 9$, to $3$ for $10\leq j\leq 12$, and to $2$ for $13\leq j\leq 15$, as confirmed by WA here. Making the appropriate substitutions, we get that the number $T_{j,1/16}$ of cubes that can be placed in the different layers, from $j=1$ to $15$, are $740$, $732$, $724$, $693$, $673$, $636$, $604$, $561$, $508$, $441$, $384$, $316$, $241$, $160$, and $77$, respectively, as shown here, here, and here. This leads to a total of $T_{1/16}=7490$, corresponding to $91.4\%$ of the total set of $8192$ cubes. This is again not sufficient to put all cubes in the bowl using this arrangement.

$\textbf{The case z=4}$. Now let us try with $z=4$. We obtain $2^{16}=65536$ cubes with side $h=1/32$ and volume $1/32768$. In this case our arrangement will have $j_{max,1/32}=1/(1/32)-1=31$ layers. Proceeding again as above, we have that the value of $k_{max,j,1/32}$ is:

$ \left\{ \begin{array}{ll} 9 & 1\leq j\leq 12 \\ 8 & 13\leq j\leq 17 \\ 7 & 18\leq j\leq 22\\ 6 & 23\leq j\leq 24\\ 5 & 25\leq j\leq 27 \\ 4 & 28\leq j\leq 29\\ 3 & j=30\\ 2 & j=31\\ \end{array} \right. $

as shown here. Making the appropriate substitutions, we get that the number $T_{j,1/32}$ of cubes that can be placed in the different layers are, according to the value of $j$:

• from 1 to 12: $3113, 3097, 3093, 3052, 3032, 3004, 2964,$ $2913, 2869, 2800, 2732, 2669$;
• from 13 to 17: $2581, 2500, 2413, 2321,2216$;
• from 18 to 22: $2097, 1992, 1877, 1752, 1616$;
• from 23 to 24: $1477, 1333$;
• from 25 to 27: $1176, 1032, 868$;
• from 28 to 29: $693, 529$;
• for j=30: $353$;
• for j=31: $177$.

Note that in the links to WA calculations it was necessary to shift the values of $j$ to obtain a result, so that in each link only the first results of the table, starting from $j=1$, have to be considered.

This leads to a total of $T_{1/32}=64341$, corresponding to 98.2% of the total set of $65536$ cubes. This is still not sufficient to put all cubes in the bowl using this arrangement.

$\textbf{The case z=5}$. Finally, let us try with $z=5$ additional triple cuts. We obtain $2^{19}=524288$ cubes with side $h=1/64$ and volume $1/262144$. In this case our arrangement will have $j_{max,1/64}=1/(64)-1=63$ layers. To avoid an excessively long list of numbers in the text, I summarized the cube count for each layer in the following table:

The total count of cubes in our arrangement is $T_{1/64}=531466$, which is larger than our set of $524288$ cubes to be placed. This means that, in the case $z=5$, we have sufficient room to put all cubes in the bowl using a total of $4+3\cdot 5=19$ cuts. Assuming, in a more realistic way, to fill the bowl in its normal position with the curved base facing downwards, therefore starting from the smaller layer ($j = 63$) and continuing in sequence with increasingly larger layers, the final arrangement of this solution would completely fill all the layers except the major one ($j = 1$), which would be filled only for $56.9\%$.

As already pointed out, it is likely that this solution is quite far from the optimal one. In addition, it has the limitation that it would not be applicable in the real world, as cutting the noodles in such a high number of very small cubes (for example, assuming a radius of 10 cm for the bowl, we would manage more than half a million of cubes with side of about 1.5 mm) is not feasible. Moreover, although the "two breaks" assumption may be in line with many cutting problems, it further moves the solution away from a realistic approach. Interestingly, however, this solution relates the OP with the problem of packing cubes in sphere, which still does not have a solution for the value of the empty volume that remains empty near the sperical surface after optimal packing.