Problem
Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that.
Solution
The solution to this is very simple, if you know mathematics. :P
Number of pieces p
p = ( n^2+n+2)/2
p = C(n+1,2) + 1
```
More on wikipedia - [http://en.wikipedia.org/wiki/Lazy\_caterer%27s\_sequence](http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence).
Proof
When a circle is cut _n_ times to produce the maximum number of pieces, represented as _p_ = _ƒ_(_n_), the _n_th cut must be considered; the number of pieces before the last cut is _ƒ_(_n_ − 1), while the number of pieces added by the last cut is _n_.
To obtain the maximum number of pieces, the _n_th cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the _n_th line itself is cut in _n_ − 1 places, and into _n_ line segments. Each segment divides one piece of the (_n_ − 1)-cut pancake into 2 parts, adding exactly _n_ to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.
Thus, the total number of pieces after _n_ cuts is
f(n) = n + f(n-1)
This [recurrence relation](http://en.wikipedia.org/wiki/Recurrence_relation "Recurrence relation") can be solved. If _ƒ_(_n_ − 1) is expanded one term the relation becomes
f(n) = n + n-1 + f(n-2)
Expansion of the term _ƒ_(_n_ − 2) can continue until the last term is reduced to _ƒ_(0), thus,
f(n) = n + n-1 + n-2 ..... + 1 + f(0)
But f(0) = 1 , because there is one piece before any cuts are made, this can be rewritten as
f(n) = 1 + (1+2+3 + .... n)
This can be simplified, using the formula for the sum of an [arithmetic progression](http://en.wikipedia.org/wiki/Arithmetic_progression "Arithmetic progression"):
f(n) = 1+ n\*(n+1)/2 = ( n^2+n+2)/2