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

http://www.cut-the-knot.com/exchange/circlecutting.html

And let me note that if you managed to obtain a formula you must be able to explain how this happened. If you are not sure than either the formula is wrong or your argument is unconvincing, like a guess. In which case you should not claim to have obtain anything.

Thank you for your quick reply. I did have a reasoning that led to the formula.

# cuts # pieces

0 1 start with 1 piece for 0 cuts
1 2
2 4
3 7

For every cut, the maximum lines you can intersect with is the previous number of cuts. So the maximum number of pieces bisected is (previous cuts 1), which is the current number of cuts. To get to the total number of pieces you have to subtract the pieces you didn't bisect, which is your previous total number of pieces minus current bisected pieces.

in formula that would be current cuts * 2 (prev total - current cuts) which is current cuts previous total

The 'previous total' is (x-1) (x-2) (x-3) .... 1 (add the one because of the original piece for 0 cuts)

This is how I got to x (x-1) (x-2) (x-3) ..... 1

I think this is correct, but since my math skills are quite rusty, and my niece's math teacher (who gave her the problem in the first place) appears to disagree with this, I thought I'd get the advice of an experienced mathematician.

Thanks a lot for your time, and I hope my explanation was not too
confusing.

Paul.

Have you checked the url I gave you?

I have, and I do not believe this is the same problem. For example, if you connect four points on the circle to each of the other points, you will draw six lines. This will give you only 8 regions. If you try to draw six lines across a circle, the maximum number of regions I believe you can get is 22.

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

Thanks a lot.

Just a clarification, the + 1 in my formula was the + 1 you thought I didn't have, I should have written:

x + x-1 + x-2 + x-3 + ... + x-x + 1

Thanks for pointing out the x·(x+1)/2 simplification. It seems to be high time I start reviewing some math before I forget everything. I have your site bookmarked and have the best intentions of reading and understanding previous postings.

Thanks again for your time,

Paul.