uniolympiads Ελληνικά

IMC 2012, Day 2, Problem 1

Consider a polynomial

f(x)=x2012+a2011x2011+⋯+a1x+a0.f(x) = x^{2012} + a_{2011}x^{2011} + \dots + a_1x + a_0.

Albert Einstein and Homer Simpson are playing the following game. In turn, they choose one of the coefficients a0,…,a2011a_0, \dots, a_{2011} and assign a real value to it. Albert 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.

Homer's goal is to make f(x)f(x) divisible by a fixed polynomial m(x)m(x) and Albert's goal is to prevent this.

(a) Which of the players has a winning strategy if m(x)=x−2012m(x) = x - 2012?

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

Original from the official PDFConsider a polynomial f (x) = x 2012 + a 2011 x 2011 + . . . + a 1 x + a 0 . Albert Einstein and Homer Simpson are playing the following game. In turn, they choose one of the coefficients a 0 , . . . , a 2011 and assign a real value to it. Albert 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. Homer’s goal is to make f (x) divisible by a fixed polynomial m(x) and Albert’s goal is to prevent this. (a) Which of the players has a winning strategy if m(x) = x − 2012? (b) Which of the players has a winning strategy if m(x) = x 2 + 1?

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Fedor Duzhin, Nanyang Technological University)

Solution. We show that Homer has a winning strategy in both part (a) and part (b).

(a) Notice that the last move is Homer's, and only the last move matters. Homer wins if and only if f(2012)=0f(2012)=0, i.e.

20122012+a2011 20122011+…+ak 2012k+…+a1 2012+a0 =0.(1)2012^{2012}+a_{2011}\,2012^{2011}+\ldots+a_k\,2012^k+\ldots+a_1\,2012+a_0\,=0. \tag{1}
Suppose that all of the coefficients except for aka_k have been assigned values. Then Homer's goal is to establish (1) which is a linear equation on aka_k. Clearly, it has a solution and hence Homer can win.

(b) Define the polynomials

g(y)=a0+a2y+a4y2+…+a2010y1005+y1006andh(y)=a1+a3y+a5y2+…+a2011y1005,g(y)=a_0+a_2y+a_4y^2+\ldots+a_{2010}y^{1005}+y^{1006}\quad\text{and}\quad h(y)=a_1+a_3y+a_5y^2+\ldots+a_{2011}y^{1005},
so f(x)=g(x2)+h(x2)⋅xf(x)=g(x^2)+h(x^2)\cdot x. Homer wins if he can achieve that g(y)g(y) and h(y)h(y) are divisible by y+1y+1, i.e. g(−1)=h(−1)=0g(-1)=h(-1)=0.

Notice that both g(y)g(y) and h(y)h(y) have an even number of undetermined coefficients in the beginning of the game. A possible strategy for Homer is to follow Albert: whenever Albert assigns a value to a coefficient in gg or hh, in the next move Homer chooses the value for a coefficient in the same polynomial. This way Homer defines the last coefficient in gg and he also chooses the last coefficient in hh. Similarly to part (a), Homer can choose these two last coefficients in such a way that both g(−1)=0g(-1)=0 and h(−1)=0h(-1)=0 hold.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?