Lazy Caterer’s Sequence

That’s an interesting name! Has an interesting concept too. Lets say you have a large cake. In N cuts, what is the maximum number of pieces you could cut this cake into, given that cuts always follow straight line? Do you have any answer for it? Well if no, maximum number of pieces follows Lazy Caterer’s Sequence.

Starting with N = 0, as N increases sequence is
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, …

Now it would be great if you could find any relation in this sequence. Did you? Well let me reveal it to you. Observe that f(n) = (n*(n+1))/2 + 1.

That made the sequence a lot simpler right? But how did this sequence come up? Lets derive it..

For any cut that you could make, you can achieve maximum number of pieces if you pass through all previous cuts. Lets say for nth cut, it should pass through all n-1 previously made cuts and at the same time not along any intersections. Thus the line itself divides into n segments each dividing their respective piece of cake into two parts. Hence for nth cut, you get n new pieces of cake. (If you are passing through an intersection of two cuts, you are loosing a piece of cake for that cut. And later on, a lot more.)

Maximum number of pieces for n cuts thus forms a recurrence relation,
f(n) = n + f(n-1).

Expanding the relation,

f(n) = n + (n-1) + f(n-2)
f(n) = n + (n-1) + (n-2) + f(n-3)
f(n) = n + (n-1) + (n-2) + ... 1 + f(0)

f(0) = 1 as there is one piece of cake when no cuts are made.

Therefore, f(n) = Sum of first n natural numbers + 1

Thus relation is f(n) = (n*(n+1))/2 + 1.


Problem related to this concept: Joyfest and Joyful Cake


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s