**Problem 4. (7 points)** \(10\) friends attend a Thanksgiving dinner party with \(2\) tables, each sitting at most \(6\) people. The chef has cut \(20\) slices of turkey and distributes the turkey amongst the friends so that each person has at least \(1\) slice and at most \(3\) slices. If \(N\) is the number of ways can he sit these people at the \(2\) tables and distribute the slices of turkey, what are the last \(3\) digits of \(N\)?

## Comments

Sort by:

TopNewestFor this problem, I will award both Jatin and Sreejato the 7 points. I apologize for the ambiguity in the problem statement. – Cody Johnson · 3 years, 8 months ago

Log in to reply

Distribution of slices doesn't depend on the distribution of people on tables, hence we will independently perform the works and then multiply, i am assuming all slices are similar, otherwise the question would be damn hard.

Let the friends be \(f_{1}, f_{2}, \dots f_{10} \)

Let no. of slices they get be \(x_{1}, x_{2} , \dots x_{10} \)

Clearly, \(\displaystyle \sum_{r=1}^{10} x_{r} = 20\), Each \(x_{r}\) satisfying \(1 \leq x_{r} \leq 3\)

No . of ways = coeff. of \(x^{20}\) in \((x^{1} + x^{2} + x^{3})^{10}\)

= coeff. of \(x^{20} \) in \(x^{10}(1 - x^3)^{10}(1 - x)^{-10}\)

= coeff. of \(x^{10}\) in \((1-x^3)^{10}(1-x)^{-10}\)

= coeff. of \(x^{10}\) in \(({10 \choose 0} - {10 \choose 1}x^3 + {10 \choose 2}x^6 - {10 \choose 3}x^9 \dots)(\displaystyle \sum_{i = 0}^{\infty} A_{i} x^{i})\)

where \(A_{i} = {(9 + i ) \choose 9}\)

Hence , no. of ways = \({10 \choose 0} \times {19 \choose 9 } - {10 \choose 1} \times {16 \choose 9} + {10 \choose 2} \times {13 \choose 9} - {10 \choose 3} \times {10 \choose 9}\)

= \(8953\).

Now, we have to arrange people (of course people are different), we make cases,

Case-1: People sit as groups of \((6,4)\), no. of ways = \({10 \choose 4} \times 2!\)

Case- 2 : People sit as groups of \((5,5)\), no. of ways = \({10 \choose 5}\).

Summing, no. of ways to arrange people = \(672\)

Hence total no. of ways = \(8953 \times 672 = 6016416 \)

Last three digits : \(\boxed{416}\) – Jatin Yadav · 3 years, 8 months ago

Log in to reply

Can you please clarify the following statement? >Case-1: People sit as groups of \((6,4)\), no. of ways = \(\binom{10}{4} \times 2! \)

From what I understand, \(\binom{10}{4}\) denotes the ways to select 4 people out of 10 people. Don't we need to arrange the selected people on the table i.e \(\binom{10}{4} \times 6! \times 4! \times 2! \)? Can you please help me clear this doubt?

Many thanks! – Pranav Arora · 3 years, 8 months ago

Log in to reply

– Jatin Yadav · 3 years, 8 months ago

Well, i thought we didn't have to arrange people on a particular table as the shape of table is not given, i mean if the table is circular , the answer is diff. and if not circular , it would be different.Log in to reply

– Pranav Arora · 3 years, 8 months ago

Ok, got it, thanks! :)Log in to reply

The wording is poor. What do you mean by "each sitting at most \ (6 ) people?" -- Can you please elaborate? – Ahaan Rungta · 3 years, 8 months ago

Log in to reply

– Cody Johnson · 3 years, 8 months ago

Self-explanatory - each table can either have 0, 1, 2, 3, 4, 5, or 6 people at it.Log in to reply

– Sreejato Bhattacharya · 3 years, 8 months ago

Does order matter? For example, do the sittings \(\{1, 2, 3, 4\}, \{5, 6, 7, 8, 9, 10\}\) and \(\{4, 3, 2, 1\}, \{9, 8, 7, 5, 6, 10\}\) count as distinct?Log in to reply

– Jatin Yadav · 3 years, 8 months ago

No, but {1,2,3,4} ,{5,6,7,8,9,10} and {5,6,78,} , {1,2,3,4,9,10} are differentLog in to reply

– Sreejato Bhattacharya · 3 years, 8 months ago

That depends on how you interpret it. OP should clarify it in his question. If selection does matter, it should read '\(10\) distinguishable friends'. If it doesn't, it should be '\(10\) identical friends'. With the current problem statement, both these interpretations are valid.Log in to reply

– Sagnik Saha · 3 years, 8 months ago

Though these problems are beyond my level of intellect, bt i think friends are always distinguishable until they are chinese.. :3 ( no offence, just on a sarcastic note)Log in to reply

– Cody Johnson · 3 years, 8 months ago

That's true. I'm sorry about that. I'll reread both of your solutions and see what I can do.Log in to reply

– Michael Tang · 3 years, 8 months ago

Also, you state that there are 2 tables in the beginning and 4 tables at the end....Log in to reply

– Cody Johnson · 3 years, 8 months ago

Sorry, 2 tables I meant.Log in to reply

\(589\) (not sure) – Sreejato Bhattacharya · 3 years, 8 months ago

Log in to reply

[Assuming order and selection don't matter]First, we note that there are \(3\) ways of sitting the friends at the tables:- this is simply the number of partitions of \(10\) where each partition can be at most \(6\). To be precise, the partitions are: \[10= 4+6= 5+5= 6+4 \] Now, let the \(i^{\text{th}}\) person receive \(a_i\) turkeys, so that \(1 \leq a_i \leq 3\), and \(\sum a_i= 20\). Using generating functions, the number of solutions is simply the coefficient of \(x^{20}\) in \[f(x)=(x+x^2+x^3)^{10}\] Note that \[f(x)= \left ( \frac{x^4-x}{x-1} \right ) ^{10} = x^{10}(x^3-1)^{10} (x-1)^{-10} \] Recall that for all \(|x|<1\), \[(x-1)^{-10}= \sum \limits_{k=0}^{\infty} \binom{9+k}{9} x^k \] The binomial expansion of \((x^3-1)^{10}\) is given by \[(x^3-1)^{10}= \sum \limits_{k=0}^{10} \binom{10}{k} (-1)^k x^{3k} \] For simplicity, let \(c_n\) denote the coefficient of \(x^n\) in \((x-1)^{-10}\), and let \(d_n\) denote the coefficient of \(x^n\) in \((x^3-1)^{10}\). Note that we have already determined the closed forms for \(c_n\) and \(d_n\): \[ \] \[\begin{array}{lcl} c_n & = & \binom{9+n}{9} \\ d_n & = & (-1)^n\binom{10}{n} \text{ ( iff } n \equiv 0 \pmod{3} \text{ )} \\ & = & 0 \text{ (otherwise)} \end{array}\]Also note that for the term \(x^{20}\) to appear in the product, the contributions from the polynomials \((x^3-1)^{10}\) and \((x-1)^{-10}\) must sum up to \(10\), since a \(x^{10}\) gets multiplied to it. We can afford to ignore the terms whose power of \(x\) is \(>20\). The coefficient of \(x^{20}\) is simply \[\sum \limits_{n=0}^{10} c_n d_{10-n} \] Note that \(d_n\) is non-zero if and only if \(n \equiv 0 \pmod{3}\), so we can simplify this summation further: \[\begin{array}{lcl} \sum \limits_{n=0}^{10} c_n d_{10-n} & = & c_{1}d_{9} + c_{4}d_{6} + c_{7}d_{3} + c_{10}d_{0} \\ & = & -\binom{10}{3} \times \binom{10}{9} + \binom{10}{2} \times \binom{13}{9} - \binom{10}{1} \times \binom{16}{9} + \binom{10}{0} \times \binom{19}{9} \\ \end{array}\] Carrying out the sum, we find out that it is equal to \(8953\). We have to multiply this with the number of sittings, giving our desired result \(8953 \times 3= \boxed{26589}\).

EDIT:Note that the problem statement is insufficient, since it doesn't state whether the friends are identical or distinguishable. I did this by assuming they are identical. If they are distinguishable, we note that any partition of the form \(10= a+(10-a)\) can be filled in \(\binom{10}{a} \) ways. Summing them over all possible partitions, we find out that the total number of selections is \[\binom{10}{6} + \binom{10}{5} + \binom{10}{4}= 672\] We have to multiply this with the total number of ways of distributing the turkeys, giving our final result \(672 \times 8953= \boxed{6016416}\). – Sreejato Bhattacharya · 3 years, 8 months agoLog in to reply

– Jatin Yadav · 3 years, 8 months ago

Hi ,friends can't be same you also have to consider their arrangement, i.e which one goes to which table.Log in to reply

– Sreejato Bhattacharya · 3 years, 8 months ago

It wasn't mentioned anywhere in the question. In a sense, both these answers are correct!Log in to reply

@jatin why u have taken two table to be distinct.... ie multiplied by 2! it might be identicle – Nishant Jha · 3 years, 8 months ago

Log in to reply

Problem 4. (7 points) friends attend a Thanksgiving dinner party with tables, each sitting at most people. The chef has cut slices of turkey and distributes the turkey amongst the friends so that each person has at least slice and at most slices. If is the number of ways can he sit these people at the tables and distribute the slices of turkey, what are the last digits of ?

why am I not able to see any figures, like at most x people or at least y slice? – Urmi Sanghavi · 3 years, 8 months ago

Log in to reply

– Michael Tang · 3 years, 8 months ago

LaTeX code doesn't work under copy-and-paste.Log in to reply

here. – Sreejato Bhattacharya · 3 years, 8 months ago

I think she means the LaTeX codes aren't loading up properly in her browser. If that is the case, I suggest you see the screenshotLog in to reply