Understanding Puzzle Patterns with Induction and Logic
Mathematical induction is a method for proving that a property defined for integers \(n\) is true for all values of \(n\) greater than or equal to some initial integer. This is done by first proving a simple case (usually called "the base case"), then also showing that if we assume that the property is true for a given case \(k^{th}\), then the next case \((k+1)^{th}\) is also true\(^{1}\). To visualize the idea of mathematical induction, imagine an infinite collection of dominoes positioned one behind the other in such a way that if any given domino falls backward, it makes the one behind it fall backward also. Then, imagine that the first domino falls backward. What happens? ... They all fall down!\(^{2}\)
In natural science courses, deduction and induction are presented as alternative modes of thought — deduction being the process of inferring a conclusion from general principles using the laws of logic, and induction being the process of enunciating a general principle after observing it to hold true in a large number of instances. The discovery of new mathematical facts often occurs through observation and experimentation with specific examples. In this sense, then, mathematical induction is not inductive but deductive. Once proved by mathematical induction, a theorem is known just as certainly as if it were proved by any other mathematical method. A mathematician with rigid standards uses inductive reasoning, in the sense applicable to natural sciences, but only to make conjectures, not to prove them. For example, observe that \(^{2}\)
$$\left( 1+\frac{1}{1} \right)=2$$
$$\left( 1+\frac{1}{1} \right)\left( 1+\frac{1}{2} \right)=3$$
$$\left( 1+\frac{1}{1} \right)\left( 1+\frac{1}{2} \right)\left( 1+\frac{1}{3} \right)=4$$
This pattern seems so unlikely to occur by pure chance that it is reasonable to conjecture that it holds true in general. In a case like this, a proof by mathematical induction gets to the essence of why the pattern holds in general. It reveals the mathematical mechanism that necessitates the truth of each successive case from the previous one. For instance, in this example, observe that if \(^{2}\)
$$\left( 1+\frac{1}{1} \right)\left( 1+\frac{1}{2} \right)\left( 1+\frac{1}{3} \right)...\left( 1+\frac{1}{k} \right)=k+1$$
Then by substitution
$$\left( 1+\frac{1}{1} \right)\left( 1+\frac{1}{2} \right)\left( 1+\frac{1}{3} \right)...\left( 1+\frac{1}{k} \right)\left( 1+\frac{1}{k+1} \right)$$
$$=\left( k+1 \right)\left( 1+\frac{1}{k+1} \right)=\left( k+1 \right)+1=k+2$$
Thus, mathematical induction makes knowledge of the general pattern a matter of mathematical certainty rather than vague conjecture. The two problems that follow are quintessential demonstrations of the application of mathematical induction to geometry*. Both start with a bit of hands-on experimentation. In the first, you can quickly gather enough evidence to make a bold conjecture about the answer to any case. The second, a little farther removed from our geometric intuition, requires the lessons learned from the first problem plus the analysis of cases with small \(n\). Needless to say, these puzzles have a lot more in common than their culinary setup!
*Strictly speaking, both problems involve a combination of defining a recurrence relation and mathematical induction.
Challenging Puzzle Examples Using Mathematical Induction
1. Cutting the Pie
With one straight cut, you can slice a pie into two pieces. A second cut that crosses the first one will produce four pieces, and a third cut (see the illustration below) can create as many as seven pieces. What is the greatest number of pieces that you can get with six straight cuts?\(^{3}\)
 |
| Image by author |
2. Slicing the Butter Cube
A cube of butter is sliced five times by a butter knife. Into how many pieces at most can the cube of butter thereby be divided if each knife stroke is perfectly straight (i.e., planar) and the pieces of butter are never rearranged? The figure below illustrates three slices, yielding eight pieces.\(^{4}\)
 |
Image by author |
Answers
1. If we try to solve the puzzle by trial and error, we may arrive at a "clever guess" for what the largest number of pieces produced by six cuts might be, but we will still have no clue as to whether that number represents a true maximum. This is analogous to knowing the mechanism by which a certain process takes place (e.g., how the motion of some object is caused by the forces involved, etc.)
When you start with an uncut pie, it counts as one piece. When the first cut is made, you add one more piece, resulting in a total of two pieces. The second cut adds two more pieces, bringing the total to four. The third cut adds three more pieces, leading to a total of seven, and so on. Each cut appears to contribute a number of pieces equal to the cut number.
On the other hand, this problem is completely equivalent to finding the maximum number of regions that can be created in the plane with \(n\) lines in general position (i.e., mutually intersecting lines, no two of which are parallel, and no three of which are concurrent). If we divide the plane into regions using \(n\) lines and draw a circle that encloses all the intersections of those lines, these regions will meet the circle in a closed area; a portion of the unbounded regions will become bounded by the circle, and the bounded ones will fall within the circle, much like the pieces of cake created by the cuts.
To explain why the number of a particular cut coincides with the number of new pieces, consider what happens when the \(k^{th}\) line. The \(k^{th}\) line meets each of the previous \(k-1\) lines; the points of intersection divide it into \(k\) segments. Consequently, the \(k^{th}\) line cuts exactly \(k\) of the regions into which the plane has already been divided. Since it divides each region through which it passes into two pieces, adding the \(k^{th}\) lines increases the number of pieces by \(k\). Thus, starting with one piece and adding \(n\) lines after that will divide the plane (or the cake) into
$$1+(1+2+3+...+n)=1+\frac{n(n+1)}{2}= \frac{n^{2}+n+2}{2} \:\: \text{by Gauss' formula & basic algebra}$$
regions. Now, we just need to let \(n=6\) and substitute this value into the formula above to get our answer,
$$\frac{6^{2}+6+2}{2}=\frac{36+6+2}{2}=\frac{44}{2}=22$$
2. First of all, note that this problem is fully equivalent to asking: Into how many parts at most can three-dimensional space be divided by \(n\) planes? This is because if you have a large enough cube to contain all the points of intersection of the planes, then each of the finitely many regions of the full-space arrangement meets the cube in exactly one convex cell. Secondly, unless one possesses an extraordinary spatial imagination, one cannot visualize all at once the pieces yielded by the \(5\) knife strokes, and even in such a case, it will not prove that whatever number one happens to get is the true maximum. A better way is to discover a law or a rule that will give the greatest number of pieces that can be obtained with any number of cuts.
To maximize the number of regions into which \(n\) planes divide three-dimensional space, we assume the planes are in general position: no two planes are parallel, any three planes must intersect at exactly one point, and no four planes can have one point in common. If these conditions are not met, the number of regions is reduced by at least one (see the diagram in the appendix at the end). We may start experimenting with what happens if we divide space using fewer planes because these cases are accessible to our geometric intuition. We also want to see whether a pattern exists.
One plane divides space into \(2\) regions. Two planes in general position partition space into \(4\) regions. Three planes divide space into \(8\) regions. You may be tempted to conclude that four planes will form \(16\) regions at most. To understand why this is not the case, imagine a tetrahedron (the three-dimensional equivalent of a triangle) floating in space, with its four face planes extended infinitely outward. In this scenario, we will consider one of these bounding planes as the newly added fourth plane, while the other three planes were already there before the new plane.
 |
| Note that the planes bounding the tetrahedron are in general position |
One region is finite, namely the interior of the tetrahedron. An infinite region may meet the tetrahedron in a face, or in an edge, or in a vertex. Hence, the total number of regions is \(1+4+6+4=15\). It appears that the three pre-existing planes "acted" as three lines in general position by dividing the fourth plane in such a way as to create \(7\) parts, each of which is a surface on which the fourth plane intersects the regions created by the previous three planes, splitting each in two and thereby forming \(7\) new regions (\(8+7=15\)). To explain this fact, let us consider the general case as follows.
Suppose there are already \(k-1\) planes arranged in general position. We may explore how adding a \(k^{st}\) plane increases the number of regions. This new plane intersects each of the existing \(k\) planes along a line. Moreover, any two lines of intersection share exactly one point in common since any three planes intersect at one point, and no three lines of intersection are concurrent. If three lines were concurrent, that would imply that at least four planes intersect at that point, which contradicts our supposition.
In consequence, these \(k-1\) lines divide the \(k^{st}\) plane into \(\frac{(k-1)^{2} + (k-1) + 2}{2}\) regions (the result of problem 1). Each one of them corresponds to a surface where the newly added plane intersects with one of the regions formed by the previous \(k-1\) planes. Hence, the \(k^{st}\) plane cuts through \(\frac{(k-1)^{2} + (k-1) + 2}{2}\) regions, dividing each region through which it passes into two pieces. Therefore, the addition of the \(k^{st}\) plane increases the number of regions by \(\frac{(k-1)^{2} + (k-1) + 2}{2}\). If we then let \(R_{k}\) be the maximum number of regions into which space can be divided by \(k\) planes, we have,
$$R_{k}=R_{k-1}+\frac{(k-1)^{2} + (k-1) + 2}{2}=R_{k-1}+\frac{k^{2} - k + 2}{2}$$
The initial condition, or base of this recursion, is 1 because before a plane is added, there is only one region, namely the whole three-dimensional space. Hence the complete recursive specification of the sequence \(R_{0}, R_{1}, R_{2}, ...\) is as follows: For all integers \(k\ge 1\),
$$R_{k}=R_{k-1}+\frac{k^{2} - k + 2}{2}$$
$$R_{0}=1$$
Here is a computation of the next five terms of the sequence:
$$R_{1}=R_{0}+\frac{1^{2} - 1 + 2}{2}=1+1=2$$
$$R_{2}=R_{1}+\frac{2^{2} - 2+ 2}{2}=2+2=4$$
$$R_{3}=R_{2}+\frac{3^{2} - 3+ 2}{2}=4+4=8$$
$$R_{4}=R_{3}+\frac{4^{2} - 4+ 2}{2}=8+7=15$$
$$R_{5}=R_{4}+\frac{5^{2} - 5+ 2}{2}=15+11=26$$
Therefore, the maximum number of pieces into which the cube of butter can be divided by five knife strokes is \(26\).*
*Note that these computations agree with our initial analysis in search for a pattern. It is left as an exercise for the reader to show that for each integer \(n\ge 1\), the maximum number of parts into which 3D space is divided by \(n\) planes has the closed form \(\frac{n^{3}+5n+6}{6}\).
Appendix
 |
| This image is not mine. It appears in Math Stack Exchange, but I've forgotten the exact discussion. |
References:
1. Mathematical induction. (2025, August). Wikipedia. Retrieved August 16, 2025, from https://en.wikipedia.org/wiki/Mathematical_induction
2. Epp, S.S. (2011). Discrete Mathematics with Applications. 4th Edition, Brooks/Cole Cengage Learning, Boston, 246-259.
3. Adapted from Gardner, M. (1961, October). Entertaining Mathematical Puzzles. Dover Publications. p. 26 (PDF version).
4. Adapted from Hoeflin, R. K. (1985, April). Problem 35 in The Mega Test. Omni, 7(4), p. 129.
Comments
Post a Comment