Piece(s) of Cake?

After qualifying for the AIME exam, Jane Street ended up delivering a specialized t-shirt for me! The back of the t-shirt reads a math problem that I found particularly interesting…

Let’s say we’re at a birthday party with a piece of cake, and you decide to randomly cut the cake n times. How many regions of the cake should we expect after those n random cuts? Maybe the cake would look something like this after 4 cuts:

Figure 1: Example of n=4 cuts, giving us 10 regions of cake!

We can quickly reshape this problem a bit: “Given a circle with n randomly drawn chords, what is the expected number of regions in the circle?” — In this scenario, we’ve changed our cake into a circle and each cut is represented by a randomly drawn chord (we’ll refer to chords as “lines” for the rest of the article). Let’s break our problem down a bit by testing smaller numbers of n and keeping track of our results:

We draw 3 lines with only one intersection as seen in the image below:

Figure 2: n = 3 lines with 1 intersection, giving 5 regions!

This gave us 5 regions! You can try this with many other amounts of lines and intersections — 4 lines and 2 intersections give us 7 regions, 3 lines and 2 intersections give us 6 regions. Clearly, there’s something going on here: with n lines and i intersections, we always end up obtaining n + i + 1 regions! R = n + i + 1 where R is the number of regions.

Now, we just need to find i — the expected number of intersections given n lines. We know that intersections must require 2 lines, so there are n choose 2 pairs of lines that could give us an intersection. What’s the probability that a random pair of lines will intersect? Well, a pair of lines is formed from 4 random points on the circle that correspond to the endpoints of the lines.

Figure 3: The three cases of forming a pair of chords given 4 randomly chosen endpoints.

This image shows the 3 cases of forming pairs of lines given 4 random endpoints. We can thus see that only 1 of the 3 cases gives an intersection, meaning we have a 1/3 probability of an intersection between 2 randomly drawn lines.

Thus, for each of the n choose 2 = (n)*(n-1)/2 pairs of lines, there’s a 1/3 chance of that pair having an intersection meaning the expected number of intersections is 1/3 * (n)*(n-1)/2 = 1/6*(n)*(n-1). This gives us our i value for expected number of intersections!

Piecing (get it?) it all together, we have R = n + 1/6*(n)*(n-1)+1 which simplifies nicely to (n+2)*(n+3)/6. So now, the next time you go to a birthday party with a cake being cut n times (randomly), you know the expected number of pieces to be left after the n cuts!