My Weblog

Blog about programming and math

Project Euler 121

I did not code this problem and compute the answer with hand. I took little bit help from sci.math. In this problem the probability after 15 turns will be total number of favorable case [ all the cases in which number of blue is more than red ] / total number of cases. Since total number of case is 16! = 20922789888000[ remember its 16!. After first round we have 2 cases,after 2nd 6cases] which is almost impossible to enumerate to count favorable cases. Drawing a ball in every turn is completely independent of each other [independent events] so we can use generating function to count the number of favorable cases. This event can be represent as generating function (x+1)(x+2)……….(x+n) where n is number of round played. You can simply test it. First you try to generate the tree model of this event up to four levels and compare it with (x+1)(x+2)(x+3)(x+4). The coefficient of x^4 represent all the blue balls taken , x^3 3 blue ball and one red ball , x^2 2 blue and 2 red , x 1 blue and 3 red and constant is all four red in 4 rounds. So favorable case for game played upto round 15 will be , if all the 15 balls are blue , 14 B 1R , 13 B 2 R, ………………… 8B,7R. Sum all the coefficients of generating function upto power 8. Maximum prize fund will be reverse of probability that 16!/favorable cases. 20922789888000/9219406943

Advertisements

August 13, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: