Distributing a cake cut with four vertical slices among three people

A round cake was cut with a knife $4$ times vertically in such a way that it is cut to maximum number of pieces.Find the number of ways of distributing these cakes among three people such that everyone gets at-least one piece.

My attempt: Maximum number of regions formed by $n$ straight lines in a plane is given by $1+\sum_{i=1}^n (i)$,so here the maximum cuts possible is $11$ now to me it seems that the rest is to count number of surjections between two sets of cardinality $11$ and $3$ respectively, which is $3! \times$StirlingS$2[11, 3]=3^{11} -3 \times 2^{11} + 3$.

But the answer says it is to be $3^{11} -3(2^{11}+1)$My instructor says that this is correct and he explains it as follows:

The total number of ways of distributing these cake pieces to $3$ people = $3^{11}$

This includes $3\times2^{11}$ ways of distributing the cake pieces in which one person will not get any cake pieces, and $3$ ways of distributing $11$ cake pieces in which only one person will get all the cake pieces.

Therefore,the required number of ways = $3^{11} -3(2^{11}+1)$.

But I am quite sure that I haven't committed any mistake in recognizing the model but I couldn't find a flaw in his reasoning either, also I couldn't convince myself why the counting surjections is not working here?!

-
The "vertical" part is throwing me off. If you want to make 11 pieces, shouldn't you necessarily make slant cuts? – Srivatsan Sep 2 '11 at 20:09
@Srivatsan: I think this is just to avoid "cute" answers. For example, to cut a cylindrical cake into 8 identical pieces with 3 cuts, cut along a diameter of the circular faces; then along the diameter orthogonal to the first cut; then with a cut parallel to the circular faces halfway up the cylinder. The "vertical" is there to disallow that third cut or cuts like it. – Arturo Magidin Sep 2 '11 at 20:16
The answers person has troubles with minus signs. But then who doesn't? – André Nicolas Sep 2 '11 at 20:18
@Arturo Well, I was confused because I didn't imagine those cute answers at all. In fact, all this while, I was visualizing a flat cake hung vertically, like a wall hanging :-) . – Srivatsan Sep 2 '11 at 20:43
@Andre It's not a minus sign trouble, it's an inclusion-exclusion or double counting trouble. – Srivatsan Sep 2 '11 at 20:46

You are correct: the answer should be $3^{11}-3\times 2^{11} +3 = 171006$ not $3^{11}-3\times 2^{11} -3 = 171000$.

There are various other ways of finding this apart from noting these are surjections: one is the inclusion-exclusion principle where the signs alternate, so ${3\choose 3}3^{11} - {3\choose 2}2^{11} + {3\choose 1} 1^{11} - {3\choose 0}0^{11}=171006$.

Another would be to find how many ways exactly two people get some cake. This is $3\times (2^{11}-2)= 6138$ (three ways of choosing which person is left out, and you have to exclude the possibilities that only one of the remaining pair gets something). So you get $3^{11} - 3\times(2^{11} -2) - 3\times1^{11}=171006$.

-
Nicer explanation. :) I liked your last paragraph that counts exactly two people getting cake. – Srivatsan Sep 2 '11 at 20:47
@Henry:The second paragraph is exactly how I counted the surjections.If A,B are non-empty sets of cardinality $m$,$n$ with $m \ge n$.Then there are $$\sum_{i=0}^{n} (-1)^i {n \choose i} (n-i)^m \text{ onto functions in } f \colon A \to B$$ – Quixotic Sep 2 '11 at 20:56
OK, I had read your preference as $n! \times \text{StirlingS2}[m,n]$, though they amount to the same thing. – Henry Sep 2 '11 at 21:25

I think the OP's answer is correct. As the OP notes, we only need to find the number of surjections $f : \{ \mathrm{Slice}_1, \mathrm{Slice}_2, \ldots, \mathrm{Slice}_{11} \} \to \{ \mathrm{Child}_1, \mathrm{Child}_2, \mathrm{Child}_3 \}$. This is equal to $$3! \cdot S(11,3)$$ where $S(\cdot, \cdot)$ refers to Stirling numbers of the second kind (wikipedia link). This turns out to be $3^{11}-3 \cdot 2^{11}+3$.

Another way to do this is using the principle of inclusion-exclusion(link).

• Let $N_0$ be the number of functions without any restriction. This is equal to $3^{11}$.

• Let $N_1$ be the number of functions $f$ such that a particular fixed element (say $\mathrm{Child}_1$) of the codomain is not in the range of $f$. This is equal to $2^{11}$, since you pick one of the remaining 2 children for each slice.

• Let $N_2$ be the number of functions such that 2 fixed elements (say $\mathrm{Child}_1$ and $\mathrm{Child}_2$) are not in the range. This number is, of course, equal to $1$ (give all slices to the lucky third child).

• Let $N_3$ be the number of functions such that all the elements of the codomain are not in the range. This is equal to $0$. (After all, we are not throwing away cake.)

So, applying inclusion-exclusion, the number of surjective functions turns out to be: $$\binom{3}{0} N_0 - \binom{3}{1} N_1 + \binom{3}{2} N_2 - \binom{3}{3} N_3 = N_0 - 3N_1 + 3N_2.$$ This confirms OP's answer.

Notice that we are adding $3N_2$ rather than subtracting it, because a function of "level 2" in the above set of definitions is automatically also present in level 1 and level 0. My guess is official solution did not do the accounting carefully.

-
:Thanks for your answer,could you find a flaw in the instructor's reasoning? – Quixotic Sep 2 '11 at 20:49
@FoolForMath My last paragraph is a weak attempt at doing that. I think Henry's answer does a good job of explaining what went wrong. Read and tell us if you need more explanation. – Srivatsan Sep 2 '11 at 20:51
The instructor overcounted the number of ways two people could each get cake – Henry Sep 2 '11 at 20:51
@Srivatsan Narayanan:It is clear now,on a different note,It seems I have some troubles in understanding different ways of counting using mutual inclusion-exclusion,abstracting through Stirling numbers works in some cases,and I am comfortable in easier problems,do you know any resource where I could get more problems on mutual inclusion and exclusion (preferably solved)? – Quixotic Sep 2 '11 at 21:02
@FoolForMath Sorry, I am not sure I am of much help here. Why don't you post this as a separate question? :) – Srivatsan Sep 2 '11 at 21:05