Thursday, November 26, 2015

Probabiliy II: Who has the winning strategy?

Consider a polynomial

$$P(x)=a_0+a_1x+\cdots+a_{2011}x^{2011}+x^{2012}$$
Nigel and Jessica are playing the following game. In turn, they choose one of the coefficients $a_0,\,\cdots,\,a_{2011}$ 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)=x^2+1$?

This problem has been answered by Mark as well!

Below is what Mark has provided for us:

We see that:

[MATH]m(\pm i)=0[/MATH]

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

[MATH]r\equiv\sum_{k=0}^{1005}\left((-1)^ka_{2k}\right)+1[/MATH]

[MATH]s\equiv\sum_{k=0}^{1005}\left((-1)^{k+1}a_{2k+1}\right)[/MATH]

And so we now see that:

[MATH]P(i)=r+si[/MATH]

[MATH]P(-i)=r-si[/MATH]

Since Jessica requires that $P(\pm i)=0$, she needs to ensure that [MATH]r=s=0[/MATH]. 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