What if robots cut your pizza?

This Riddler puzzle is about random chords of a circle and the regions they describe.

At RoboPizza™, pies are cut by robots. When making each cut, a robot will randomly (and independently) pick two points on a pizza’s circumference, and then cut along the chord connecting them. If you order a pizza and specify that you want the robot to make exactly three cuts, what is the expected number of pieces your pie will have?

Here is a simple solution, which was pointed out to me in a comment to my original post.
[Show Solution]

The following solution is a bit more complicated, and computes the entire distribution rather than just its expected value.
[Show Solution]

If you’ve already read the solution above and you’re interested in the distribution of pieces for the general case, read on!
[Show Solution]

9 thoughts on “What if robots cut your pizza?”

  1. I like your solution, though (as always) since Catalan numbers showed up I’ll have to re-read the whole thing.

    I am a bit surprised that I haven’t seen anyone take the approach of just solving for the probability of any two chords intersecting — using the Beta Formula (times 2 choose 1)– and then having linearity of expectations take you the rest of the way home for any n number of chords. It’s worth mentioning that the Beta Formula, while being an integral, has a very nice discrete probability derivation.

    A link to my solution is below:
    https://www.dropbox.com/s/2whl4k8f6eel96r/solution_robo_pizza2_.jpg?dl=0

    Cheers

    1. That’s a great question; I was thinking about making a separate post about this. It turns out that while using linearity of expectation as you describe gives the correct answer, the logic is flawed. Although the chords are independent, pairs of chords are not independent.

      If the approach were valid, you could use the same argument to derive the entire probability distribution, which would be a binomial distribution. For example, the probability of having three intersections should be $(\tfrac{1}{3})^3 = \tfrac{1}{27}$. But if you use the approach I describe in my solution, you get a probability of $\tfrac{1}{15}$ instead!

      Edit: I’m wrong about this! see comment below.

      1. On the contrary, it is a primary feature of the Linearity of Expectations that independence is not required.

        For review, you may consider reading the first 3 pages of
        http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/readings/ln14.pdf

        Especially notice the quote on page 2 “The great thing about linearity of expectation is that no independence is required. This is really useful, because dealing with independence is a pain, and we often need to work with random variables that are not independent.”

        And then see how it is applied in The Hat-Check Problem on page 3, using indicator random variables. The Hat Problem involves sampling without replacement (i.e not binomial).

        I believe Bertsekas and Tsitsiklis cover this in some detail in their book on probability.

        1. You’re absolutely right. You can indeed use linearity of expectation to find the expected number of intersections. No independence assumption is required there. I think I might edit my post to include this new answer — thanks!

          Finding the general distribution is more difficult however because there independence matters.

  2. Dear Professor Lessard,

    I have recently gotten into trying to work on the Riddler problems posted weekly. I could not solve this past week’s problem and am now trying to work on understanding your solution that you have posted. I have several questions.

    Firstly, why do you state that we can ignore the scenario of three intersecting chords? That’s a theoretically possible option I believe?

    Secondly, how do you determine that V=2n+ p vertices?

    Thank you very much in advance for your response,
    Michael

    1. We can ignore the case where three chords meet in a single point because the probability of that happening is vanishingly small. If you were to fix five of the six endpoints, there is only one point on the circumference where you can put the sixth endpoint so that all three chords intersect at the same point. Since there are infinitely many points on the circumference, the probability of that point being chosen is zero.

      We have $n$ chords and $p$ intersections. Each intersection is a vertex ($p$ in total), and both endpoints of each chord is a vertex ($2n$ in total).

  3. Thank you for the beautiful problem and solution!

    I think there is a typo in the first approach (based on Euler’s formula), but the final answer (S = n + p + 1) is correct.

    “V=2n+pV=2n+p vertices (count the ones on the circumference). Each internal intersection adds an edge, and we must count the arcs between cuts along the circumference as edges, so we have a total of E=3n+p.”

    Correction: each internal intersection adds 2 edges, so E = 3n + 2p.

Leave a Reply

Your email address will not be published. Required fields are marked *