Efficient Pizza-cutting


题目

一张圆形披萨,用10条直线去切,最多能切成多少块?

分析

要让块数最多,每一刀都应满足两件事:

  1. 这条新切线要与之前每一条切线都相交。
  2. 任意三条切线不共点(避免把多个交点重合成一个)。

\(n\)刀如果与前\(n-1\)刀都有不同交点,就会被分成\(n\)段,从而新增\(n\)块。

设最多块数为\(P_n\),则有递推:即\(P_n=P_{n-1}+n\)。且\(P_0=1\)(不切时只有1块)。

所以\(P_n=1+\sum_{k=1}^{n}k=1+\frac{n(n+1)}{2}\)

代入\(n=10\),得\(P_{10}=1+\frac{10\cdot11}{2}=1+55=56\)

Previous Next