LAST EDITED ON Nov-01-00 AT 10:32 AM (EST)

>Msg=What is the maximum number of pieces you can
>get cutting a circle x times.

>I came up with x + (x-1) + (x-2).... + 1
>but I'm not sure this is correct.

Check this. For x = 0, 1, 2, 3, 4 you must get 1, 2, 4, 7, 11, respectively. Your formula simplifies to (just by induction)

F(x) = x + (x-1) + (x-2).... + 1 = x·(x + 1)/2

with

F(0) = 0
F(1) = 1
F(2) = 3
F(3) = 6
F(4) = 10

1 short every time. It appears that the correct formula may rather be

G(x) = x·(x + 1)/2 + 1

The reasoning is very much yours. The max number of crossings is the previous number of lines. The number of added regions is 1 more than the number of new crossings. Let G(x) be the max number of regions after x cuts. Then

G(x) = G(x-1) + (x-1) + 1 = G(x-1) + x

Use this recursively as you did:

G(x) = G(x-2) + x + (x-1)
G(x) = G(x-3) + x + (x-1) + (x-2)
...
G(x) = G(0) + x + (x-1) + (x-2) + ... + 1
= 1 + x + (x-1) + (x-2) + ... + 1
= 1 + x·(x + 1)/2

That's all.

All the best,
Alexander Bogomolny