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]

11 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.

  4. Hello Professor Lessard,

    First, thanks for this great post!

    I had a question about this paragraph:

    “One final point of interest: the way in which the chords are randomly chosen is important! If we had used a different method, e.g. by picking a random radius and a random point on that radius, and then constructing a chord perpendicular to the radius through this chosen point, then we would obtain a different answer! The approach above works because the way the chords are chosen allows us to decouple how endpoints are chosen from how labels are assigned”

    I’ve been reading into Bertrand’s Paradox, and literature on ‘solutions’, including Edwin Jaynes’ solution focusing on a solution that is both scale and translation invariant. Given alternative methods of empirically deriving the likelihood that two chords intersect, from what you wrote:

    “The approach above works because the way the chords are chosen allows us to decouple how endpoints are chosen from how labels are assigned”

    it reads like you chose this method because of the way it would “specify” the randomness. Can you speak more to how you chose this?

    Given the result from the n=2 case and the results from Riordan’s generating function, it seems that there is a “correct” specification of randomness when empirically simulating the likelihood that two chords intersect, is there a way to assert that one methodology is more correct than another, as I understood you did when you implied that “picking a random radius and a random point on that radius, and then constructing a chord perpendicular to the radius through this chosen point” would result in an incorrect answer?

    Thanks again!

    1. Hi Miguel, thanks for the comment.

      The method for randomly selecting the chords was specified in the problem statement, so I did what the problem asked. My point was merely that the way in which we choose chords is very important, and had they specified a different way of selecting the chords, the problem would have a different solution.

      I did not mean to imply that there is one way of randomly selecting chords that is “more correct” than another. What I meant was that if you select the chords differently from how the problem says you should, you’ll get a different answer, and it would be “incorrect” because it’s not what the question asked for.

      I hope this clears things up!

Leave a Reply

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