What is the largest number of pieces you can get by cutting a pizza

[wubie]

Hello,

I am trying to follow an example/explanation, but with no luck. Here is the question:

What is the largest number of pieces you can get by cutting a pizza with n straight vertical cuts if the pieces are not to be moved between cuts?

Let n be the number of cuts and let a_n be the maximum number of pieces.

Now it is clear that a₀ = 1 and a₁ = 2. Since we want to maximize the number of pieces, we ensure that two cuts cross. Hence, a₂ = 4.

(Now here is the part in the example where I get confused):

Similarly, a third cut should cross both of the previous two, but not where they cross each other. This yields a₃ = 7.

How did they do that? I don't understand. Wait a minute, I think I do understand how they did it. But, the pieces couldn't be equal could they? Is it possible to make three cuts, get seven pieces, but have all seven pieces equal?

The example goes further:

Suppose n - 1 cuts have been made and a_{n - 1} pieces are obtained. As before, the n-th cut should cross each of the others at distinct points. Hence there will be n - 1 points of intersection on it, dividing it into n segments. Each segment cuts an existing piece into two. Hence we get the recurrence relation

a_n = a_{n - 1} + n, 1 <= n

a₀ = 1.

Ok. I didn't understand this part. Could someone reword this for me if it isn't too much trouble? I can't see what they are saying as of yet.

Any help is appreciated. Thankyou.

 

[HallsofIvy]

Wait a minute, I think I do understand how they did it. But, the pieces couldn't be equal could they? Is it possible to make three cuts, get seven pieces, but have all seven pieces equal?

Don't go off on a tangent. Was there anything in the problem that said the pieces were SUPPOSED to be equal?

Suppose n - 1 cuts have been made and an - 1 pieces are obtained. As before, the n-th cut should cross each of the others at distinct points. Hence there will be n - 1 points of intersection on it, dividing it into n segments. Each segment cuts an existing piece into two. Hence we get the recurrence relation

an = an - 1 + n, 1 <= n

a0 = 1.

There are n-1 cuts, meaning the pizza is crossed by n-1 lines. Your new cut will be a straight line. One straight line can't cross another twice, but if you are very careful, your new cut can cross every cut already made once. Since your new line is crossing n-1 lines, that will make n-1 points on your new line where the other cross it. That actually divides the new line into n segments (think about that: 1 point on a line divides it into 2 parts. 2 points on a line divide it into 3 parts, etc.
Of course, the section between two of the "old" cuts was a piece of pizza. Your new cut divides that piece into two pieces. Suppose the pizza had already been cut into 7 pieces (thats what I got dividing a circle by 3 lines) and your new cut crosses 4 of those pieces (i.e. crosses all 3 old lines). One way of counting the new number of pieces is to say "3 of the pieces were not cut. 4 we divided in two (NOT of equal size- the problem says nothing about "equal") by the new cut- that's 8 pieces. We now have 3+ 8= 11 pieces. It's easier, however, to say that there are 4 "new" pieces, counting 1 of the 2 halves of the divided piece as the "old" piece. 7 "old" pieces plus 4 "new" pieces is 11 just as before. If there were n-1 cuts, making a_n pieces, adding a new cut that crosses each of the old ones divides n "old" pieces in two, effectively adding n "new" pieces. a_n= a_n-1+ n.

Look at this from the start: with 0 cuts, you have 1 piece. Adding 1 new cut, so that n=1, you divide the pizza into 2 pieces. A second cut crosses that first cut once, of course, meaning that your second cut crosses 2 pieces, adding 2 pieces to the previous total: a₂= a<sub>1+ 2= 2+2= 4. The third line crosses both previous lines and, so, crosses 3 pieces, dividing them in two and creating 3 "new" pieces: a3= a2+ 3= 7 pieces.
Hope that helps.

Of course, with 0 cuts, the pizza is in one piece: a0= 1.</sub>

 

[M98Ranger]

Hello,

The question is asking for the maximum number of pieces that can be obtained by cutting a pizza with n straight vertical cuts, without moving the pieces between cuts. To solve this problem, we use a recurrence relation, which is a mathematical equation that relates each term in a sequence to the previous term(s).

In this case, we have a sequence of the number of pieces obtained after each cut, starting with a0 = 1 for the initial cut, a1 = 2 for the first cut, and so on. To understand the solution, let's look at the example with three cuts. The first two cuts are made to create four pieces, as you mentioned. For the third cut, we want it to cross both of the previous cuts at different points, so that it creates a total of seven pieces. This is achieved by making the third cut in between the first two cuts, creating two additional pieces on each side. This results in a total of seven pieces, with each piece being a different size.

To generalize this for n cuts, we use the same approach. We make the nth cut in between the previous n-1 cuts, creating n-1 points of intersection and n segments. Each segment cuts an existing piece into two, resulting in n additional pieces. This is represented in the recurrence relation an = an-1 + n, where n represents the number of the current cut.

I hope this explanation helps clarify the solution. Let me know if you have any further questions.