數學歸納法 (10分)

Before doing M.I. , let's make some observation first.
Let a be the number of cutting made, i be the number of intersection of cutting and Na be the maxium number of pieces obtained. We have
a=1 then i=0 and N1=2
a=2 then i=1 and N2=4
a=3 then i=3 and N3=7
a=4 then i=6 and N4=11

Claim: A new cutting which make K intersection will generate exactly K+1 new pieces.
Proof: K intersection is corresponding to K non-intersecting cutting made and hence K+1 pieces was made. A K-intersection cutting will just double the total number of pieces.

Now, we could proceed the M.I.
This is already true for a=1, 2, 3 and 4.
Suppose this is true for k where k is less than or equal to 4, then
N(k) = (k^2+k+2)/2
For the (k+1)th cutting, in order to maximize the number of pieces made, the new cutting must intersect the previous k cutting. By the Claim, there will be exactly k+1 new pieces made. Hence,
N(k+1)
= { (k^2+k+2)/2 } + k+1
= (k^2+3k+4)/2
= ( {k+1}^2+{k+1} +2)/2

This completes the proof.

2006-11-27 23:51:39 補充：
SORRYProof: The new K-intersection is corresponding to K non-intersecting cutting made previously and hence K+1 pieces was previously made. A K-intersection cutting will just double the total number of pieces.