Ukrainian Mathematical Olympiad

Question

Two players play the following game. They start with the polynomial 2013x^2 + 2012x + 2011 and take moves by turns. During each move a player subtracts from the polynomial one of the following polynomials: x^2, x, x^2 - x + 1 or x^2 + x - 1, at his choice. If after a player's move the polynomial has an integer root, he loses. Which of the players has a winning strategy?

Accepted Answer

Доведемо, що виграє перший гравець. Він може ходити так, щоб після його ходу вільний член одержаного многочлена був непарним, а коефіцієнти при x^2 та x мали однакову парність (для цього він може спочатку відняти від многочлена x^2, а далі повторювати ходи другого гравця). Тоді після ходів першого гравця будуть з'являтися квадратні тричлени, які в цілих точках приймають лише непарні значення, а тому не мають цілих коренів. Отже, перший гравець не програє. Зазначимо, що з кожним ходом сума коефіцієнтів одержаного многочлена зменшується на 1. Через декілька ходів ця сума стане рівною 0, а тоді одержаний многочлен матиме корінь x = 1. Відтак, гра гарантовано закінчиться і виграє перший гравець.