CMC - Problem 4

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

Note by Cody Johnson
5 years, 10 months ago

No vote yet
12 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

For this problem, I will award both Jatin and Sreejato the 7 points. I apologize for the ambiguity in the problem statement.

Cody Johnson - 5 years, 10 months ago

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 - 5 years, 10 months ago

Log in to reply

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

Michael Tang - 5 years, 10 months ago

Log in to reply

Sorry, 2 tables I meant.

Cody Johnson - 5 years, 10 months ago

Log in to reply

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

Cody Johnson - 5 years, 10 months ago

Log in to reply

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

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

@Sreejato Bhattacharya No, but {1,2,3,4} ,{5,6,7,8,9,10} and {5,6,78,} , {1,2,3,4,9,10} are different

jatin yadav - 5 years, 10 months ago

Log in to reply

@Jatin Yadav That depends on how you interpret it. OP should clarify it in his question. If selection does matter, it should read '1010 distinguishable friends'. If it doesn't, it should be '1010 identical friends'. With the current problem statement, both these interpretations are valid.

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

@Sreejato Bhattacharya That's true. I'm sorry about that. I'll reread both of your solutions and see what I can do.

Cody Johnson - 5 years, 10 months ago

Log in to reply

@Sreejato Bhattacharya 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)

Sagnik Saha - 5 years, 10 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 f1,f2,f10f_{1}, f_{2}, \dots f_{10}

Let no. of slices they get be x1,x2,x10x_{1}, x_{2} , \dots x_{10}

Clearly, r=110xr=20\displaystyle \sum_{r=1}^{10} x_{r} = 20, Each xrx_{r} satisfying 1xr31 \leq x_{r} \leq 3

No . of ways = coeff. of x20x^{20} in (x1+x2+x3)10(x^{1} + x^{2} + x^{3})^{10}

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

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

= coeff. of x10x^{10} in ((100)(101)x3+(102)x6(103)x9)(i=0Aixi)({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 Ai=((9+i)9)A_{i} = {(9 + i ) \choose 9}

Hence , no. of ways = (100)×(199)(101)×(169)+(102)×(139)(103)×(109){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}

= 89538953.

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

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

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

Summing, no. of ways to arrange people = 672672

Hence total no. of ways = 8953×672=60164168953 \times 672 = 6016416

Last three digits : 416\boxed{416}

jatin yadav - 5 years, 10 months ago

Log in to reply

Hello Jatin!

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

From what I understand, (104)\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 (104)×6!×4!×2!\binom{10}{4} \times 6! \times 4! \times 2! ? Can you please help me clear this doubt?

Many thanks!

Pranav Arora - 5 years, 10 months ago

Log in to reply

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.

jatin yadav - 5 years, 10 months ago

Log in to reply

@Jatin Yadav Ok, got it, thanks! :)

Pranav Arora - 5 years, 10 months ago

Log in to reply

589589 (not sure)

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

[Assuming order and selection don't matter] First, we note that there are 33 ways of sitting the friends at the tables:- this is simply the number of partitions of 1010 where each partition can be at most 66. To be precise, the partitions are: 10=4+6=5+5=6+410= 4+6= 5+5= 6+4 Now, let the ithi^{\text{th}} person receive aia_i turkeys, so that 1ai31 \leq a_i \leq 3, and ai=20\sum a_i= 20. Using generating functions, the number of solutions is simply the coefficient of x20x^{20} in f(x)=(x+x2+x3)10f(x)=(x+x^2+x^3)^{10} Note that f(x)=(x4xx1)10=x10(x31)10(x1)10f(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, (x1)10=k=0(9+k9)xk(x-1)^{-10}= \sum \limits_{k=0}^{\infty} \binom{9+k}{9} x^k The binomial expansion of (x31)10(x^3-1)^{10} is given by (x31)10=k=010(10k)(1)kx3k(x^3-1)^{10}= \sum \limits_{k=0}^{10} \binom{10}{k} (-1)^k x^{3k} For simplicity, let cnc_n denote the coefficient of xnx^n in (x1)10(x-1)^{-10}, and let dnd_n denote the coefficient of xnx^n in (x31)10(x^3-1)^{10}. Note that we have already determined the closed forms for cnc_n and dnd_n: cn=(9+n9)dn=(1)n(10n) ( iff n0(mod3) )=0 (otherwise)\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 x20x^{20} to appear in the product, the contributions from the polynomials (x31)10(x^3-1)^{10} and (x1)10(x-1)^{-10} must sum up to 1010, since a x10x^{10} gets multiplied to it. We can afford to ignore the terms whose power of xx is >20>20. The coefficient of x20x^{20} is simply n=010cnd10n\sum \limits_{n=0}^{10} c_n d_{10-n} Note that dnd_n is non-zero if and only if n0(mod3)n \equiv 0 \pmod{3}, so we can simplify this summation further: n=010cnd10n=c1d9+c4d6+c7d3+c10d0=(103)×(109)+(102)×(139)(101)×(169)+(100)×(199)\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 89538953. We have to multiply this with the number of sittings, giving our desired result 8953×3=265898953 \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+(10a)10= a+(10-a) can be filled in (10a)\binom{10}{a} ways. Summing them over all possible partitions, we find out that the total number of selections is (106)+(105)+(104)=672\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×8953=6016416672 \times 8953= \boxed{6016416}.

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

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

jatin yadav - 5 years, 10 months ago

Log in to reply

@Jatin Yadav It wasn't mentioned anywhere in the question. In a sense, both these answers are correct!

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

@jatin why u have taken two table to be distinct.... ie multiplied by 2! it might be identicle

Nishant Jha - 5 years, 10 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 - 5 years, 10 months ago

Log in to reply

LaTeX code doesn't work under copy-and-paste.

Michael Tang - 5 years, 10 months ago

Log in to reply

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 screenshot here.

Sreejato Bhattacharya - 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...