0

A mega pizza is to be sliced $n$ times,and $S_n$ denotes maximum possible number of pieces.

I got $S_1 = 2 $ , $S_2 =4 $ , $S_3 =7 $ , $S_4 =11 $...

Comparing these we can say that $S_n=S_{n-1}+n$

So, $S_n=n+(n-1)+(n-2) \dots +2$

But is there a better way to do this?

Bernard
  • 175,478
user69608
  • 858
  • Yes, $S_3=8$ by slicing the top off ;) – user10354138 Jul 26 '20 at 18:18
  • 1
    It is supposed to be a thin Italian pizza, not the Chicago simulation. – markvs Jul 26 '20 at 18:20
  • How do you prove your guessed recurrence relation? – Bernard Jul 26 '20 at 18:29
  • 1
    "Comparing these we can say that Sn=Sn−1+n" For $n \le 4$. Unless we can explain why we can't exptrapolate. $S_1=2$ so $S_n=n+1$. Oops $S_2=4$ so $S_n=2n$. $S_3=7$ so $S_{2k-1}=2k-1;S_{2k}=2k+1$ and $S_4=11$ so$S_n=3n-1,2,2,1,2,2,1...$. So the question is why* does doing the $n$th slice add $n$ more slices? – fleablood Jul 26 '20 at 18:36

2 Answers2

1

It’s not too hard to prove that recurrence. The best that you can do is make the $(n+1)$-st cut cross each of the first $n$ cuts. That means that it cuts through $n+1$ of the pieces formed by the first $n$ cuts, dividing each of them into $2$ pieces and leaving unchanged any other pieces formed by the first $n$ cuts. This increases the number of pieces by $n+1$, so $S_{n+1}=S_n+n+1$ or, equivalently, $S_n=S_{n-1}+n$.

For the closed form you can note that $S_0=1$, so in general

$$S_n=1+\sum_{k=0}^{n}k=1+\frac{n(n+1)}2\;.$$

Brian M. Scott
  • 616,228
1

I would prove the recurrence formula geometrically:

The number of supplementary pieces with $n+1$-th slicing is equal to the number of supplementary regions created in the plane when you add an $n+1$-th line to a set of $n$ lines in general position (i.e. no two lines parallel, no three lines through the same point).

This number is equal to the number of regions in $S_n$ crossed by the newline, which is equal to the number of intervals created by the $n$lines on the new one. As there are $n$ distinct intersection points, this means $n+1$ intervals, hence $n+1$ new regions in the plane. Therefore $$S_{n+1}=S_n+ n+1.$$

Bernard
  • 175,478