11176 - Winning Streak

[Robert Gerbicz]

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]

Yes, my polynomials are wrong. Thanks for pointing that out.

[tkcn]

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?

Thanks in advance.

[tkcn]

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.