Puzzle time - slicing the pie

[jon-nyc]

What's the maximum number of pieces you can get by cutting a (round) pie with 10 straight cuts, from edge to edge?  The pieces don't need to be wedges, nor do they have to be all the same size.

[Klaus]

Upper bound: 2^10.
Lower bound: 11.

[Klaus]

A wild guess:

Ceiling((11*12)/3) = 44

[Klaus]

My (sloppy) reasoning:

||
The first elements of the "max parts after n cuts" sequence seem to be 1,2,4,7,10,14,19. That's the beginning of A007980, whose description sounds vaguely related to the problem. It's 11th element is what I wrote above.
||

[jon-nyc]

That’s not the answer and that’s not the series. Also 10 cuts not 100.

[Klaus]

Yeah, I corrected the # of cuts. Still not right? I'm trying to avoid actually thinking.

[jon-nyc]

It’s not. Still the wrong series.

[Klaus]

OK, here's what all other sequences that start with 1,2,4,6,10,14,19 stored at that nice website say about it's 10th/11th element:

A023115 - 45
A076101 - 52
A094281 - 51
A323623 - 43
A023536 - 46
A047808 - 44
A076268 - 42
A024536 - 49
A117237 - 52

It must be one of those

[jon-nyc]

Hint:

||Thinking of the cuts as lines on a circle, what’s the largest number of lines the nth cut can intersect?||

[jon-nyc]

@Klaus said in Puzzle time - slicing the pie:

OK, here's what all other sequences that start with 1,2,4,6,10,14,19 stored at that nice website say about it's 10th/11th element:

A023115 - 45
A076101 - 52
A094281 - 51
A323623 - 43
A023536 - 46
A047808 - 44
A076268 - 42
A024536 - 49
A117237 - 52

It must be one of those

And it’s none of those!

[Klaus]

@jon-nyc said in Puzzle time - slicing the pie:

Hint:

||Thinking of the cuts as lines on a circle, what’s the largest number of lines the nth cut can intersect?||

Hey, I'm in a Zoom meeting right now. I can only do this as a low-priority background task that doesn't require me to think

[Klaus]

||
Oh, I see, my problem was that I screwed up on the start of the sequence. It's 1,2,4,7,11,16.

The first answer I get from OEIS is A000124, which has the promising subtitle "maximal number of pieces formed when slicing a pancake with n cuts.".

So the answer seems to be 56.

I refer to the references given at OEIS for the rationale
||

[jon-nyc]

Cheater.

||How about noticing, based on my hint, that the nth cut can, at most, intersect the other n-1 cuts just once. That forms n new line segments (considering the edges of the pizza as end points as well). Each new line segment corresponds to a new slice of pie.

So f(n)=f(n-1)+n
And we know f(0) is 1

So:
f(1) = 2
f(2) = 4
f(3) = 7
f(4) = 11
f(5) = 16
f(6) = 22
f(7) = 29
f(8) = 37
f(9) = 46
f(10) = 56

So to get the nth number:

1+1+2+3+4+5+6..+n

Note that's just 1 plus the sum of the natural numbers to n.

So 1 + n(n+1)/2 or

(n^2 + n + 2)/2||

[Klaus]

Hey, I didn't google for the task or something; I merely tried out a few cuts and searched for known sequences based on that. For a 5% CPU usage background task I'm happy with my performance

[Klaus]

@jon-nyc said in Puzzle time - slicing the pie:

How about noticing, based on my hint, that the nth cut can, at most, intersect the other n-1 cuts just once.

That makes sense, but how do you know that this is not merely an upper bound but that you can always find a line that intersects n-1 cuts?

[jon-nyc]

The short answer I can give you on my phone is “because there are infinite points on a circle”.

If you want a longer explanation I can do that later.