Thursday, November 12, 2015

Probabiliy: 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-2012$?

Solution provided by Mark, another contributor from this blog:

In order to win, Jessica wants to have at the end (since she has the last move):

[MATH]P(2012)=0[/MATH]

or:

[MATH]\sum_{k=0}^{2011}\left(a_k2012^k\right)+2012^{2012}=0[/MATH]

or:

[MATH]\sum_{k=0}^{2011}\left(a_k2012^k\right)=-2012^{2012}[/MATH]

No matter what values Nigel and Jessica have chosen for the first 2,011 coefficients, all Jessica has to do is choose for the last ($a_\ell$ where $0\le\ell\le2011$) which can be obtained from:

[MATH]\sum_{k=0}^{\ell-1}\left(a_k2012^k\right)+a_{\ell}2012^{\ell}+\sum_{k=\ell+1}^{2011}\left(a_k2012^k\right)=-2012^{2012}[/MATH]

Solving for $a_{\ell}$, we find:

[MATH]a_{\ell}=-\frac{1}{2012^{\ell}}\left(\sum_{k=0}^{\ell-1}\left(a_k2012^k\right)+\sum_{k=\ell+1}^{2011}\left(a_k2012^k\right)+2012^{2012}\right)[/MATH]

With this value for $a_{\ell}$, Jessica is assured of winning the game.