Thursday, November 26, 2015

Probabiliy II: Who has the winning strategy?

Consider a polynomial

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:



And so we now see that:



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