3
$\begingroup$

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?!

  • 1
    @FoolForMath: Instructor's answer is wrong, after we remove the at least one person gets $0$ cases, we must *add back* the two people $0$ cases that have been double removed. It really is very basic Inclusion-Exclusion, the signs alternate.2011-09-03

2 Answers 2

2

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$.

  • 0
    OK, I had read your preference as $n! \times \text{StirlingS2}[m,n]$, though they amount to the same thing.2011-09-02
3

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.

  • 0
    @Andre Ok. I was just concerned that we are now so deep in the comment stack that your explanation will probably not be seen by future visitors... :)2011-09-03