How do you cut it?
Introduction
The circle cutting problem is a famous puzzle that attempts to find the maximum number of pieces formed by N cuts through a circle. This question has been solved numerous times through the euler formula or recursion. This question is an excellent introduction to these ideas and is really cool counting problem. However to those amongst who are really bored, you may wonder what if we didn’t restrict ourselves to the 2D plane, but instead the 3D real world. Or maybe, some of you may be incredibly bored and may think, what if we generalized this to N dimensions. In other words:
What is the maximum number of “pieces” that can be formed by cutting an N dimensional solid with k cuts?
This questions reveals a very interesting counting relation and is interesting to work through. The solution I will present to you will involve logic, geometry, and a little bit of counting and recursion. This solution will also consist of three parts: 2D (recap), 3D, and N dimensions.
Assumptions
Before we begin cutting spheres in 4D space we have to lay down a few basic assumptions to solve this problem:
- Each cut goes on forever and is straight. This essentially just means that we cut straight and don’t stop. The cuts don’t end or curve for our convenience.
- The figure we start off with is convex. This essentially means every cut splits a piece in exactly two. This means we can freely switch between a circle and a square. The figure below shows the reason behind this assumption:
These assumptions will hold for all dimensions.
Rules
There are two rules that we will follow in order to maximize the number of pieces. Both of them are sort of obvious but important. These rules will hold in all dimensions but I will explain them in 2D
- Intersection points have a maximum of two lines going through them. This is because if there were three lines going through one, we could just move one line off the intersection point and make another shape.
- No lines are parallel. This rule exists because if they were parallel we can move one line so they intersect at a point. This intersection creates another shape. This motivates the idea that to maximize pieces we maximize intersection points
2D case
External vs Internal Pieces
To make our problem a bit easier I define an external piece as a piece that touches the edge of the figure, and an internal piece as a piece that is fully enclosed by other pieces.
It is easy to see that:
\[n_{total} = n_{external} + n_{internal}\]External pieces?
To find the number of external pieces we consider \(k\) lines going through the center at a single point. There are currently \(2k\) pieces. We then shift each line off center so we comply with the two rules above. Since no new line is going through the external figure, the maximum number of pieces is still \(2k\)
Internal pieces
The number of internal pieces is a bit tricky but we first note that the internal shape at the center of the \(k\) cuts is an \(k\) sided polygon. For example with 3 cuts there’s a triangle in the middle, with four cuts there’s an irregular trapezoid. Now the lines that make this internal polygon will intersect outside the internal shape and make new internal pieces. The next step is to find the total number of such extra internal pieces. To do this we pick a side and find there are \(k-3\) remaining sides to pick from. We do this for all \(k\) sides, resulting in \(k(k-3)\) total combinations. However we are overcounting exactly twice and thus divide by two to get the final answer of extra internal pieces:
\[n_{internal} = \frac{k(k-3)}{2} + 1\]Final answer for 2D
\(n_{total} = \frac{k(k-3)}{2} + 1 + 2k\)
3D case
Our strategy will remain pretty much the same but working from the internal piece. Before we begin, here are some basic observations
- Three planes intersect in a point, two planes intersect in a line.
- Maximize number of intersection points results in the maximum number of pieces (combines our rules from above)
Strategy
We start off with \(k\) cuts and the resulting \(k\) sided figure in the center. There are \(k\) points on this figure. What’s interesting to note is the when counting the separate pieces, the boundary of the external, original figure also can also be used to build the pieces.
- The first set of pieces I will consider are the pieces formed by three planes from the internal figure. \(n_{1} = \binom{k}{3}\)
- The second set of pieces are the ones that are formed by the lines that are created by from the lines eminating from the internal figure. These pieces are growing out of the original figure and there are a maximum of \(k\) of them.
- Now we consider the pieces that are created from the intersection of these eminating corner pieces. Each pair of these corner pieces can interesect to form a piece. It is important to note that these pieces may share a border with the external, original shape. The maximum amount of these are \(n_{3} = \binom{number of corner pieces}{2} = \binom{k}{2}\)
- Lastly we count the internal piece which is just \(1\) piece.
The total sum is therefore: \(n_{total} = \binom{k}{3} + \binom{k}{2} + \binom{k}{1} + \binom{k}{0}\) \(= \frac{k^3 + 5k^2 + 6}{6}\)
Any dimensional case
Our experience with the third dimension hints at a possible pattern for the N dimensions but before begin, I would like to introduce a recursive method that will allow us to check our work so far.
Recursive solution
When we are living in 0D every “cut” doesn’t change the point
| Dimension | Cuts: 0 | Cuts: 1 | Cuts: 2 | Cuts: 3 | Cuts: 4 |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
When we are one dimension, each “cut” just adds one more piece.
| Dimension | Cuts: 0 | Cuts: 1 | Cuts: 2 | Cuts: 3 | Cuts: 4 |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 |
For 2D and 3D we use our formulas from above.
| Dimension | Cuts: 0 | Cuts: 1 | Cuts: 2 | Cuts: 3 | Cuts: 4 |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 1 | 2 | 4 | 7 | 11 |
| 3 | 1 | 2 | 4 | 8 | 15 |
The recursive formula is thus: \(n_N^k = n_{N-1}^{k-1} + n_{N}^{k}\) Where \(n\) is the number of pieces, \(N\) is the dimension, and \(k\) is the number of cuts.
Let’s try and develop some intution for why this works. Suppose we have \(k\) cuts in \(N\) dimensions. When we do our next cut with a (\(N-1\) dimension plane), we try and intersect as many pieces as possible. After doing the cut we examine the number of pieces in our \(k+1\)th \(N-1\) dimension plane. The number of pieces on this plane is equal to the number of new pieces in our original \(N\) dimensional figure. It’s interesting to note that the powers of 2 are popping up as we move down, more on that when we derive our final result.
Finding the formula through recursion is left as an exercise to the reader.
Final solution
Like with all solutions before, we start off with the \(N\)-dimensional internal piece with \(k\) sides/faces/ \(N-1\)-dimesional analog. For example in 3D and 4 slices results in a tetrahedron in the middle.
Lattice point pieces
When \(k\) slices occur in the \(N\) dimensional shape there are \(p_1\) points of intersection or lattice points where \(p_1\) is:
\[p_{1} = \binom{k}{N}\]Each lattice point can result in a single piece. We say a lattice point piece is piece that eminates from a lattice point. This results in: \(p_1\) pieces. It is important to note that these lattice point pieces don’t have to be connected to internal pieces.
Dropping dimensions to count
Whenever a lattice point piece is created, there are pieces formed in the intersection of these lattice point pieces. When \(N-2\) intersections of the \(N-1\) dimensional slices we get a line. For example, when two planes intersect they create a line. Our next set of pieces will be from these lines. Another way of thinking of thinking about these pieces are the pieces formed by the intersection of pieces eminating from the internal shape (step 2 in our 3D case). The goal becomes to find the number of lines, since each line corresponds to a newly formed piece. A basic counting argument reveals:
\[p_{2} = \binom{k}{N-1}\]Our next set of pieces are the result of when \(N-3\) \(N-1\) dimensional slices intersect (that was a mouthful). In 3D these are just the remaining pieces that aren’t formed by lattice point or intersections of lattice point pieces. These are actually easy to spot, with them being the face pieces of our original interal piece. In 3D there are \(k\) such pieces, but in general there are:
\[p_{2} = \binom{k}{N-2}\]We can extend this pattern for all \(N\) dimensions, with
\[p_{d} = \binom{k}{N-d}\]Provided \(N-d > 0\)
Lastly our final piece is our original internal piece. This is just a +1 on our current sum.
We sum up all \(p_i\) to get the total pieces.
Final solution and remarks
\[n_{t} = \sum_{i=0}^{N} \binom{k}{i}\]Checking the recursion pattern shows this formula works! What I find cool about this result is how as the dimension gets really high, the number of pieces approaches \(2^k\). This makes intuitive sense because everytime we add a dimension there is a new way to cut every single piece in half, thus doubling the number of pieces.
Stepping back, this problem may seem kind of niche and uninteresting, but it’s a cool way to see how certain properties remain the same as our dimension grows. A simple problem, a simple solution.
See you next time!