Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
@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
1  
The answers person has troubles with minus signs. But then who doesn't? –  André Nicolas Sep 2 '11 at 20:18
1  
@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
1  
@Andre It's not a minus sign trouble, it's an inclusion-exclusion or double counting trouble. –  Srivatsan Sep 2 '11 at 20:46

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
Nicer explanation. :) I liked your last paragraph that counts exactly two people getting cake. –  Srivatsan Sep 2 '11 at 20:47
1  
@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.

share|improve this answer
    
: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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.