25
$\begingroup$

Today while making dinner consisting of instant noodles, I thought of the most ridiculous question I've ever asked this site.

The Instant Noodle Problem

Suppose you are a college student preparing one of those cuboid-shaped instant noodle packages. You plan on breaking the noodles such that each piece can be entirely submerged by boiling water (i.e; below the top of the bowl).

noodles and bowl

The noodles have dimensions $2\times2\times\frac{1}{2}$, thus having volume $$V_{n}=2$$ Meanwhile the bowl is a hemisphere of radius $1$ $$V_{b}=\frac{2\pi}{3}\approx2.094$$

Clearly, the bowl has just enough room to fit the noodles. Accordingly,

What is the minimum planar-breaks required to fit the noodles in the bowl?

I imagine this is a tough problem, perhaps playing out like the moving sofa problem. Hence I plan on rewarding a 250 point bounty to most efficient solution / tightest bounds or an answer with exemplary research.

$\endgroup$
  • $\begingroup$ Have you found a solution yourself? $\endgroup$ – razivo Jul 28 at 10:40
  • 3
    $\begingroup$ Nice to see this kind of problems ! $\to +1$ $\endgroup$ – Claude Leibovici Jul 28 at 10:46
  • 5
    $\begingroup$ @razivo I ended up crunching the whole packet into the bowl. Oh, mathematically? Currently working on an upper bound. $\endgroup$ – Graviton Jul 28 at 10:50
  • 2
    $\begingroup$ Not that I have any idea how to solve the problem :) but if I make $2$ cuts, in x- and y- directions down the center, resulting in four $1 \times 1 \times 1/2$ pieces, does this count as $2$ breaks or $3$ breaks? (In a cake cutting problem this usually counts as $2$ cuts, but instant noodles are usually broken up by hand and you may have to break it $3$ times in this case: Break original, break left piece, break right piece.) $\endgroup$ – antkam Jul 30 at 18:01
  • 3
    $\begingroup$ I believe that the 3 breaks version works well, and it is easy to relate the number of pieces to the number of breaks (simply add one to number of pieces): c.f. the answer to this chocolate breaking problem —the answer generalises to this instance. $\endgroup$ – Good Boy Aug 3 at 12:37
3
+250
$\begingroup$

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.

enter image description here

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:

enter image description here


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

enter image description here

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

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:

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Exactly the approach I started to attempt in getting a rough upper bound. Regardless of it's efficiency or applicability, 19 cuts is excitingly low. This answer is a great read. I salute the dedication and work you've put forth, graphics and all! I wonder how easily (or not) this could be optimized to leave some of the cubes that are eventually placed into larger cuboids with this method uncut. $\endgroup$ – Graviton Aug 4 at 6:27
  • 1
    $\begingroup$ Surely the method could be optimized by leaving some cuboids uncut. Just as an example, after the four initial cuts we can take one of the sixteen $\frac 12 \times \frac 12 \times \frac 12$ cubes and place it in the center of the basal part of the arrangement, leaving it uncut and continuing the sequence of cuts with the others. This may lead to some minimal changes in some layers (particularly those where the central square has a side formed by a odd number of small cubes) but should not alter the final result. $\endgroup$ – Anatoly Aug 4 at 9:34
  • 1
    $\begingroup$ Similarly, when we arrive to the cubes with side $1/8$, we could place some of them around the central cube, e.g. adjacent to the central part of its lateral faces. This kind of optimizations would not reduce the number of cuts needed for the final arrangement, but could simplify the procedure. $\endgroup$ – Anatoly Aug 4 at 9:37
  • $\begingroup$ nice - I will apply this approach to my nightly, half-drunk indomie routine and see if it helps. $\endgroup$ – dezdichado Aug 5 at 22:26
  • $\begingroup$ Cutting cubs in half i.e. triangular prisms, seems, will give more flexibility. $\endgroup$ – zkutch Aug 6 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.