uniolympiads English

IMC 2012, Ημέρα 2, Θέμα 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?

Πρωτότυπο από το επίσημο 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?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 1. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;