Two players play the following game. They start with the polynomial and take moves by turns. During each move a player subtracts from the polynomial one of the following polynomials: , , or , 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?
Solution
Доведемо, що виграє перший гравець. Він може ходити так, щоб після його ходу вільний член одержаного многочлена був непарним, а коефіцієнти при та мали однакову парність (для цього він може спочатку відняти від многочлена , а далі повторювати ходи другого гравця). Тоді після ходів першого гравця будуть з'являтися квадратні тричлени, які в цілих точках приймають лише непарні значення, а тому не мають цілих коренів. Отже, перший гравець не програє. Зазначимо, що з кожним ходом сума коефіцієнтів одержаного многочлена зменшується на 1. Через декілька ходів ця сума стане рівною 0, а тоді одержаний многочлен матиме корінь . Відтак, гра гарантовано закінчиться і виграє перший гравець.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.