That Friend

Probability Level pending

Three of my friends and I are going to split the bill for dinner. Bill and I will each contribute an odd number of dollars, while Celia contributes a number of dollars that is a multiple of 3 3 . Nikhil will either contribute nothing, or steal \textbf{steal} one or two dollars. In how many ways can we pay a $ 30 \$30 bill?


The answer is 136.

Alan Yan by Alan Yan , 20, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Alan Yan
Sep 7, 2015

The generating function for this scenario is

( x + x 3 + . . . ) 2 ( 1 + x 3 + x 6 + . . . ) ( x − 2 + x − 1 + 1 ) = 1 + x + x 2 ( 1 − x 2 ) 2 ( 1 − x 3 ) (x+x^3+...)^2(1+x^3+x^6+...)(x^{-2}+x^{-1}+1) = \frac{1+x+x^2}{(1-x^2)^2(1-x^3)}

1 + x ( 1 − x 2 ) 3 = 1 ( 1 − x 2 ) 3 + x ( 1 − x 2 ) 3 = ∑ k = 0 ∞ ( k + 2 2 ) x 2 k + x ∑ k = 0 ∞ ( k + 2 2 ) x 2 k \frac{1+x}{(1-x^2)^3} = \frac{1}{(1-x^2)^3} + \frac{x}{(1-x^2)^3} = \sum_{k= 0}^{\infty}{{k+2 \choose 2}x^{2k}} + x\sum_{k=0}^{\infty}{{k+2 \choose 2}x^{2k}}

The right term does not have a x 30 x^{30} term so we just need to worry about the left term.

The coefficient of the x 30 x^{30} term is ( 17 2 ) = 136 {17 \choose 2 } = \boxed{136} .

Note: since the answer is so nice, \textbf{Note:} \textit{ since the answer is so nice, }

can you come up with a counting argument? \textit{can you come up with a counting argument?}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...