Processing math: 100%

Thursday, November 26, 2015

Probabiliy II: Who has the winning strategy?

Consider a polynomial

P(x)=a0+a1x++a2011x2011+x2012

Nigel and Jessica are playing the following game. In turn, they choose one of the coefficients a0,,a2011 and assign a real value to it. Nigel has the first move. Once a value is assigned to a coefficient, it cannot be changed any more. The game ends after all the coefficients have been assigned values.

Jessica's goal is to make P(x) divisible by a fixed polynomial m(x) and Nigel's goal is to prevent this.

Which of the players has a winning strategy if m(x)=x2+1?

This problem has been answered by Mark as well!

Below is what Mark has provided for us:

We see that:

m(±i)=0

So, in light of the cyclical nature of integral powers of i, let us define:

r1005k=0((1)ka2k)+1

s1005k=0((1)k+1a2k+1)

And so we now see that:

P(i)=r+si

P(i)=rsi

Since Jessica requires that P(±i)=0, she needs to ensure that r=s=0. And so a winning strategy for Jessica is to always follow Nigel with a pick of coefficients in the same sum (either r or s) with the same number but with a subscript of opposing parity to produce a pair adding to zero. When Nigel picks his last coefficient in the sum within r, Jessica needs to subtract 1 from his choice as her last pick in this sum. She could actually choose to subtract 1 from any of Nigel's choices as one of her choices within r.

In this way, Jessica can ensure her winning strategy.


No comments:

Post a Comment