# Sword, pizza and watermelon

Suppose that we have a sword and cut a pizza and watermelon. What is the maximum number of pieces of pizza or watermelon obtained after 10 cuts. Is there a general formula

-
For the pizza, see this. – Willie Wong Jul 11 '12 at 12:12
For the watermelon, see this. – Willie Wong Jul 11 '12 at 12:15

If you are given a plane then, maximum number of pieces after $n$ cuts is given by recursion $$C(n)=C(n-1)+n$$ with $C(1)=2$ which evaluates to $C(n)=1+\frac{n(n+1)}{2}$. I think this same formula gives the answer of your problem(for pizza). For watermelon, we need to consider 3-D space, the recursion for maximum number of pieces after $n$ cuts is $D(n)=D(n-1)+C(n-1)$ which can be evaluated easily with $D(1)=2$. Explanation for recurrence of $C(n)$: Suppose there are already $n$-cuts, so when we add a new cut, to maximize the number of pieces, we have to cut without 3-lines being concurrent and no 2-lines should be parallel. When these conditions are satisfied, then new cut when passes through a region divides it into $2$ parts giving $1$ part extra and the number of region it passes is $n$(you can check that for small $n$), thus giving total $n$ extra regions$\implies C(n)=C(n-1)+n$. Similar reasoning works for the 3-D case(watermelon) but you need to handle that case carefully.

-
Can you explain how to get these recurrences – Adi Dani Jul 11 '12 at 12:47

You can get 1024 of each by rearranging pieces between cuts to all be cut in half with the next cut. In fact, this is exactly how I make my famous samurai-ninja-watermelon-pizza salad, though I recommend skinning the rind from the watermelon first.

Note: I've also found that you can get even more pieces of pizza if you fold it like a kid's paper snowflake between cuts, but I've never personally made it over 8,192 pieces with this method...

-