Loon Cutting Puzzle: Max Pieces Formula and Proof

Martin Gardner's "Colossal Book of Mathematics" features a puzzle about cutting a paper crescent moon (technically called a "loon") with a knife. The goal is to determine the maximum number of pieces that can be created with a given number of cuts, where each cut goes all the way through the moon and can be placed anywhere.

The Pancake Problem: A Simpler Analogy

To understand the moon puzzle, it's helpful to first consider a simpler, classic problem: cutting a pancake.

• Zero cuts: 1 piece
• One cut: 2 pieces
• Two cuts: 4 pieces
• Three cuts: 7 pieces (not 8, as one might initially think)
• Four cuts: 11 pieces

The key to maximizing pieces in the pancake problem is ensuring each new cut intersects all previous cuts. The number of new pieces added with each cut increases by one more than the previous cut (e.g., +2, then +3, then +4).

This sequence (1, 2, 4, 7, 11, 16...) is known as the "pancake sequence." The formula for the number of pieces with n cuts is n + 1 choose 2 + 1, which is a triangular number plus one. If you subtract one from these numbers, you get the triangular numbers: 1, 3, 6, 10, 15, 21, etc.

The Cake Problem: A 3D Extension

A similar problem involves cutting a cake (a 3D object). If you make cuts all the way through, the number of pieces follows a cubic sequence. For example, with five cuts on an egg (representing a cake), you might see 14 pieces on the surface, but there are actually 15 pieces in total, including a "nugget" or "kernel" in the middle. The goal is to maximize the number of pieces, regardless of their size.

The Loon Problem: Maximizing Pieces

Returning to the crescent moon:

• Zero cuts: 1 piece
• One cut: 3 pieces
• Two cuts: 6 pieces

The trick to maximizing pieces in the loon is to ensure all intersections of the cuts occur within the moon's surface.

Visualizing the Solution

Imagine the crescent moon has an internal "pancake" region where the cuts intersect. The strategy is to:

1. Make all cuts such that they maximize the number of pieces within this central "pancake" region, following the pancake problem's logic.
2. Ensure these cuts continue across the "Gulf of Mexico" (the empty space between the two arcs of the crescent) and intersect the other side of the moon.

It's often easier to draw the cuts first and then draw the crescent moon around them to ensure optimal intersections.

Counting the Pieces for the Loon

Let's analyze the number of pieces for the loon with n cuts:

• Pancake Region: The central region of the moon, where all cuts intersect, will yield n + 1 choose 2 + 1 pieces, just like the pancake problem.
• Additional Pieces: Each cut, after passing through the "pancake" region, will then cross the other arc of the moon, creating n additional pieces.

Example with 3 cuts:

1. Pancake pieces: For n=3, the pancake formula gives 3 + 1 choose 2 + 1 = 4 choose 2 + 1 = 6 + 1 = 7 pieces.
2. Additional pieces: These 3 cuts will create 3 more pieces on the other side of the moon.
3. Total: 7 + 3 = 10 pieces.

Example with 4 cuts:

1. Pancake pieces: For n=4, the pancake formula gives 4 + 1 choose 2 + 1 = 5 choose 2 + 1 = 10 + 1 = 11 pieces.
2. Additional pieces: These 4 cuts will create 4 more pieces.
3. Total: 11 + 4 = 15 pieces.

The sequence for the loon is: 1 (0 cuts), 3 (1 cut), 6 (2 cuts), 10 (3 cuts), 15 (4 cuts), and so on. These are the triangular numbers: 3, 6, 10, 15... The formula for the number of pieces with n cuts is n + 2 choose 2, or (n + 2) * (n + 1) / 2.

Proving Optimality with Euler's Formula

This solution is optimal, meaning it yields the maximum possible number of pieces. This can be proven using Euler's formula for planar graphs: Regions = Edges - Vertices + 1.

To apply Euler's formula, we consider the moon and its cuts as a graph:

• Vertices (V): These are the points where cuts intersect each other, or where cuts intersect the boundary of the moon, or the "horns" of the moon.
  • Intersections within the "pancake" region: n choose 2 (every pair of n cuts intersects once).
  • Where cuts cross the inner boundary of the crescent: n vertices.
  • Where cuts cross the outer boundary of the crescent: n vertices.
  • Where cuts enter the "southern branch" of the crescent: n vertices.
  • Where cuts exit the "southern branch" of the crescent: n vertices.
  • The two "horns" of the moon: 2 vertices.
  • Total vertices: V = n choose 2 + 4n + 2.
• Edges (E): These are the segments of the cuts or the segments of the moon's boundary.
  • The number of edges is more complex to calculate directly but is derived from the vertices and the structure of the cuts.

By calculating the number of vertices and edges in this graph, and applying Euler's formula, one can confirm that the derived formula for the number of pieces is indeed the maximum possible. The crucial aspect is ensuring that all intersections occur within the crescent moon to maximize the graph's complexity and thus the number of regions.

Moon Trees

As an interesting aside, the discussion concludes with a mention of "moon trees." These are trees grown from seeds that were taken to the moon, often planted as memorials or symbols of space exploration. The specific example given is a Coast Redwood (Sequoia sempervirens) "moon tree."