What is the maximum number of pieces a cake can be cut into using $n$ straight cuts?
I came across this interesting problem on facebook. Let us denote the maximum number in above problem by $C(n)$. If $n = 1$, then obviously $C(1) = 2$. If $n = 2$, then also obviously $C(2) = 4$. If $n = 3$, then one can convince oneself that $C(3) = 7$. For $n = 4$ and higher it become a bit difficult to arrive at the correct answer by simply hit and trial.
We now solve the problem using induction. Suppose that $n \geq 2$ and we have some configuration of $n$ straight cuts which are made along the lines $L_1, \dots, L_n$. We now make the $(n + 1)$th cut along the line $L$. Note that $L$ meets each of line $L_i$ at most once. Let us denote the point of intersection of $L$ and $L_i$ by $a_i$. If points of intersections $a_i$ are distinct, then they divide $L$ into $n + 1$ segments. Each segment bisects existing piece into two pieces. Thus the new cut introduces $n+1$ new pieces as long as $L$ is not parallel to some $L_i$ and it does not passes through a point of intersection of some $L_i$ and $L_j$ (and also that all the intersection points $a_i$ lie inside the cake). Hence, we have $$C(n + 1) = C(n) + n + 1$$ for $n \geq 2$ and so $$C(n) = \frac{n(n+1)}{2} + 1.$$
It is natural to wonder about generalization of above problem to higher dimensions: How many connected regions does $n$ hyperplanes cut $\mathbb{R}^d$ into? The answer is $$\sum_{k = 0}^{d} \binom{n}{k}.$$ This relates to the theory of hyperplane arrangments.
