## 11176 - Winning Streak

Moderator: Board moderators

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
little joey wrote:If my hand calculations are right, the first four polynomials are:

Code: Select all

``````    A(1) =   p
A(2) =  2p
A(3) =  3p - p^2 +2p^3 - p^4
A(4) =  4p -3p^2 +7p^3 -6p^4 +3p^5 - p^6
``````
There are some errors, the degree of A(k) is at most k. By a program the correct computed polynomials:

Code: Select all

``````A(1)=p
A(2)=2*p
A(3)=p^3 - p^2 + 3*p
A(4)=-p^4 + 4*p^3 - 3*p^2 + 4*p
A(5)=2*p^5 - 6*p^4 + 10*p^3 - 6*p^2 + 5*p
A(6)=-2*p^6 + 10*p^5 - 18*p^4 + 20*p^3 - 10*p^2 + 6*p
A(7)=2*p^7 - 11*p^6 + 30*p^5 - 41*p^4 + 35*p^3 - 15*p^2 + 7*p
A(8)=-p^8 + 10*p^7 - 36*p^6 + 72*p^5 - 80*p^4 + 56*p^3 - 21*p^2 + 8*p
A(9)=p^9 - 7*p^8 + 36*p^7 - 96*p^6 + 151*p^5 - 141*p^4 + 84*p^3 - 28*p^2 + 9*p
A(10)=-2*p^10 + 10*p^9 - 36*p^8 + 112*p^7 - 225*p^6 + 288*p^5 - 231*p^4 + 120*p^3 - 36*p^2 + 10*p
``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Yes, my polynomials are wrong. Thanks for pointing that out.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

tkcn
New poster
Posts: 5
Joined: Wed Apr 02, 2008 3:42 pm

### Re: 11176 - Winning Streak

Hello.
I am trying to solve this problem.
I already used DP to calculate the number of "from i consecutive games you get no more than j consecutive wins", just like Ivan said.
But I still confused how to derive the correct answer from this DP table.

My biggest problem is, for example i=3 and j=1, there are 4 cases: LLW, LWL, WLL, WLW.
The final case "WLW" has a different probabillity with orthers and I don't know how to separate them.
Can somebody give me a hint?

tkcn
New poster
Posts: 5
Joined: Wed Apr 02, 2008 3:42 pm

### Re: 11176 - Winning Streak

Hi.
Finally, I was solved this problem.
I was misunderstanding Ivan said, try to calculate the "count" of "from i consecutive games you get no more than j consecutive wins",
but what we need is the "probability".

Thanks.