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

  • 0
    Please try to make your titles descriptive of the problem; asking for people to confirm your answer may be done in the body, but "On confirming my answer" would make it hard for someone to guess what this problem is about, and useless for someone doing a backward search looking for problems that might be similar to the one they are contemplating. Thanks.2011-09-02
  • 0
    @Arturo Magidin:You are very fast!I was just editing it to :"Problem on distributing cakes among people" but then I saw "Arturo Magidin has edited the title;please refresh the problem page" this quote may not be entirely correct but the meaning is.2011-09-02
  • 1
    The "vertical" part is throwing me off. If you want to make 11 pieces, shouldn't you necessarily make slant cuts?2011-09-02
  • 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.2011-09-02
  • 1
    The answers person has troubles with minus signs. But then who doesn't?2011-09-02
  • 0
    @Srivatsan Narayanan:Sorry about the earlier comment;No,slant cuts are not allowed.2011-09-02
  • 0
    @André Nicolas:I have updated the combinatorial argument given by my instructor in support of the answer.2011-09-02
  • 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 :-) .2011-09-02
  • 1
    @Andre It's not a minus sign trouble, it's an inclusion-exclusion or double counting trouble.2011-09-02
  • 0
    @Srivatsan Narayanan: I imagined that for the third item (namely $-3$, the person decided (s)he was removing the obvious $3\times 2^{11}$, then there was the $3$ that had to be in some sense removed, and lumped them together. It is clear that the OP's answer is right, though it is unfortunate that he appeals to a formula rather than a process.2011-09-03
  • 0
    @Andre Yes, I agree. My point was that the mistake committed by the person is not an algebra mistake or a typo; it was because of applying inclusion-exclusion wrongly (and I guess we both are in agreement). Reg. the second point, the OP does seem to have a bit of a trouble with ideas like inclusion-exclusion, and prefers to work with standard formulas like here. You can read our conversation in the comments following my answer regarding this.2011-09-03
  • 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$.

  • 1
    Nicer explanation. :) I liked your last paragraph that counts exactly two people getting cake.2011-09-02
  • 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 $$2011-09-02
  • 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
    :Thanks for your answer,could you find a flaw in the instructor's reasoning?2011-09-02
  • 0
    @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.2011-09-02
  • 0
    The instructor overcounted the number of ways two people could each get cake2011-09-02
  • 0
    @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)?2011-09-02
  • 0
    @FoolForMath Sorry, I am not sure I am of much help here. Why don't you post this as a separate question? :)2011-09-02
  • 0
    I am not sure how others will react to it,may be "too-localized" and will close it ?!2011-09-02
  • 0
    @FoolForMath I would still try if I were you. You are asking for a resource. How can it be localized? I don't know how many people think like me though :)2011-09-02
  • 0
    You are a kind peroson:-) I just searched into OCW course-ware and found [this](http://ocw.mit.edu/high-school/courses/combinatorics-the-fine-art-of-counting/) Seems like it covers inclusion-exclusion too,so I guess I should try in work on those problems first before bugging others for more :-)2011-09-02
  • 0
    @FoolForMath: What's wrong in the instructor's reasoning is that his/her $3\times 2^{11}$ *includes* the ways in which two people get nothing, in fact includes all of them twice. Call the people $A$, $B$, $C$. The instructor thought $2^{11}$ for distributing between $B$ and $C$. But this counts $A=0$ and $B=0$, also $A=0$ and $C=0$. The next $2^{11}$ counts $B=0$ and $A=0$, also $B=0$ and $C=0$. The next counts $C=0$ and $A=0$, also $C=0$ and $B=0$. Each double $0$ has been counted twice! To be really persuasive, use $3$ instead of $11$. List all ways explicitly.2011-09-03
  • 0
    @Andre Perhaps you can even write an answer explaining the instructor's mistake? After all, it seems that this is the OP's real question. I don't think either my or Henry's answer directly addresses this issue.2011-09-03
  • 0
    @Srivatsan Narayanan: It is partly dealt with by your correct way of using Inclusion-Exclusion, also in Henry's second method, in which $2^{11}$ is replaced by $2^{11}-2$.2011-09-03
  • 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