gavinksong Posted August 5, 2013 Report Share Posted August 5, 2013 Hey, kids. Here's a pizza. I'm going to make N random straight cuts. Enjoy! How many pieces do you expect? Quote Link to comment Share on other sites More sharing options...

0 Anza Power Posted August 6, 2013 Report Share Posted August 6, 2013 (edited) The answer is 1+n+n(n-1)/6. Ok so assuming the random cuts are made by selecting two random numbers in the range 0-2pi and cutting a line between these two points on the circumferential of the pizza. First note that the probability of having 3 cuts intersect at the same point is 0, so we assume all intersections are between just two cuts. Also note that all the pieces that result from the cuts are convex. With these two things in mind, if there were n cuts and c intersections then the number of slices would be 1+n+c, you can convince yourself of that by looking at what happens when you slowly start making a new cut. So what is c? well for two cuts what is the probability that they intersect? if the first cut was A-B and the second was C-D, then they'd intersect if and only if the values of A B C D were ordered in one of the following forms: ACBD ADBC BCAD BDAC CADB CBDA DACB DBCA And not the following forms: ABCD ABDC BACD BADC CDAB CDBA DCAB DCBA ACDB ADCB BCDA BDCA CABD CBAD DABC DBAC. Or another way you can think of it is you choose 4 points on a circle and assign them labels ABCD with equal probability, what is the probability that AB are not neighbors? So the probability for intersection is 1/3. Let x_{i,j} be a random variable that gets value 1 if cuts i and j inttersect and 0 otherwise, it's obvious that E[x_{i,j}]=1/3. It's obvious that c=sum_over_i_and_j(x_{i,j}), we can't calculate the probability for c because x_{i,j}'s are not independant, but we can calculate it's mean because the mean is linear doesn't matter if the variables are independant or not, so: E[c] = E[sum(x_{i,j})] = sum(E[x_{i,j}]) = n(n-1)/2*E[x_{1,2}] = n(n-1)/2*1/3 = n(n-1)/6 So on average you will get 1+n+n(n-1)/6 slices Edited August 6, 2013 by Anza Power Quote Link to comment Share on other sites More sharing options...

0 harey Posted August 5, 2013 Report Share Posted August 5, 2013 (edited) 2*n. As we are conditioned to cut a pizza through the centre, each cut will double the number of pieces. As the cuts are random, the pieces will not be of same size. Edited August 5, 2013 by harey Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted August 5, 2013 Author Report Share Posted August 5, 2013 2*n. As we are conditioned to cut a pizza through the centre, each cut will double the number of pieces. As the cuts are random, the pieces will not be of same size. Nice try, harey! But you should not think it is so simple! The cuts are not necessarily through the center. Quote Link to comment Share on other sites More sharing options...

0 DeGe Posted August 5, 2013 Report Share Posted August 5, 2013 This is a good question. With every step that I take, it gets more and more complex I am probably not using the right technique! Quote Link to comment Share on other sites More sharing options...

0 Joyandwarmfuzzies Posted August 5, 2013 Report Share Posted August 5, 2013 Each time you make a random cut, you'll intersect all of the previous cuts. Some of the pieces may be very small, but there will still be a piece, as the probability of intersecting at a previous intersection is 0. The number of pieces, therefore, is one more than the sum of 1, 2, 3, 4, ..., N (since zero cuts gives you one piece), which comes out to N (N+1) / 2 + 1 Quote Link to comment Share on other sites More sharing options...

0 jamieg Posted August 5, 2013 Report Share Posted August 5, 2013 Each time you make a random cut, you'll intersect all of the previous cuts. Some of the pieces may be very small, but there will still be a piece, as the probability of intersecting at a previous intersection is 0. The number of pieces, therefore, is one more than the sum of 1, 2, 3, 4, ..., N (since zero cuts gives you one piece), which comes out to N (N+1) / 2 + 1 The cuts are random, not necessarily maximizing number of slices. Otherwise you'd be correct. Quote Link to comment Share on other sites More sharing options...

0 Joyandwarmfuzzies Posted August 5, 2013 Report Share Posted August 5, 2013 Each time you make a random cut, you'll intersect all of the previous cuts. Some of the pieces may be very small, but there will still be a piece, as the probability of intersecting at a previous intersection is 0. The number of pieces, therefore, is one more than the sum of 1, 2, 3, 4, ..., N (since zero cuts gives you one piece), which comes out to N (N+1) / 2 + 1 The cuts are random, not necessarily maximizing number of slices. Otherwise you'd be correct. Oh damn, good point. Quote Link to comment Share on other sites More sharing options...

0 BobbyGo Posted August 5, 2013 Report Share Posted August 5, 2013 Well, if the maximum number of slices is N(N+1)/2+1 and the minimum is N+1, would the expected just be the average of these two? (N(N+1)/2+1+N+1)/2 or (1/4)(n^{2}+3n+4) Quote Link to comment Share on other sites More sharing options...

0 Anza Power Posted August 5, 2013 Report Share Posted August 5, 2013 Hi. Can you please define random cuts? you are stepping into the problem in Bertrand's Paradox. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted August 6, 2013 Author Report Share Posted August 6, 2013 Hi. Can you please define random cuts? you are stepping into the problem in Bertrand's Paradox. I had random endpoints in mind, but I suppose either of the other methods might make interesting problems too. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted August 6, 2013 Author Report Share Posted August 6, 2013 Hi. Can you please define random cuts? you are stepping into the problem in Bertrand's Paradox. I had random endpoints in mind, but I suppose either of the other methods might make interesting problems too. Disclaimer: since this is an original problem, I am not quite sure of my own solution. I just tried solving the problem with the "random midpoint" and "random radius" methods. I think they may be easier (if I'm not wrong). I encourage all of you to try solving the problem using all three methods outlined in Anza Power's link. Whoever finds all three solutions wins a free compliment. Quote Link to comment Share on other sites More sharing options...

0 jordge Posted August 6, 2013 Report Share Posted August 6, 2013 Whatever the solution is, I'm sure there are more pieces than I can eat. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted August 6, 2013 Author Report Share Posted August 6, 2013 Whatever the solution is, I'm sure there are more pieces than I can eat. Well, the pizza is always the same size, regardless of how many pieces you cut it into. Quote Link to comment Share on other sites More sharing options...

0 James33 Posted August 6, 2013 Report Share Posted August 6, 2013 I think the answer will be the same as the maximum. IIIRC you get the maximum value by making cuts that don't go trough the centre and aren't the same as previous ones. The probability of this happening is 0 if you make random cuts. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted August 7, 2013 Author Report Share Posted August 7, 2013 (edited) The answer is 1+n+n(n-1)/6. Ok so assuming the random cuts are made by selecting two random numbers in the range 0-2pi and cutting a line between these two points on the circumferential of the pizza. First note that the probability of having 3 cuts intersect at the same point is 0, so we assume all intersections are between just two cuts. Also note that all the pieces that result from the cuts are convex. With these two things in mind, if there were n cuts and c intersections then the number of slices would be 1+n+c, you can convince yourself of that by looking at what happens when you slowly start making a new cut. So what is c? well for two cuts what is the probability that they intersect? if the first cut was A-B and the second was C-D, then they'd intersect if and only if the values of A B C D were ordered in one of the following forms: ACBD ADBC BCAD BDAC CADB CBDA DACB DBCA And not the following forms: ABCD ABDC BACD BADC CDAB CDBA DCAB DCBA ACDB ADCB BCDA BDCA CABD CBAD DABC DBAC. Or another way you can think of it is you choose 4 points on a circle and assign them labels ABCD with equal probability, what is the probability that AB are not neighbors? So the probability for intersection is 1/3. Let x_{i,j} be a random variable that gets value 1 if cuts i and j inttersect and 0 otherwise, it's obvious that E[x_{i,j}]=1/3. It's obvious that c=sum_over_i_and_j(x_{i,j}), we can't calculate the probability for c because x_{i,j}'s are not independant, but we can calculate it's mean because the mean is linear doesn't matter if the variables are independant or not, so: E[c] = E[sum(x_{i,j})] = sum(E[x_{i,j}]) = n(n-1)/2*E[x_{1,2}] = n(n-1)/2*1/3 = n(n-1)/6 So on average you will get 1+n+n(n-1)/6 slices This is correct. One down, two to go. These should be pretty easy after looking at Anza's solution. Edited August 7, 2013 by gavinksong Quote Link to comment Share on other sites More sharing options...

## Question

## gavinksong

Hey, kids.

Here's a pizza. I'm going to make N random straight cuts. Enjoy!

How many pieces do you expect?

## Link to comment

## Share on other sites

## 15 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.