Maths Olympiad Prep

Library / /69 of 121

Combinatorics Difficulty 6.2 National Olympiad Prove it India

Problem:

Written on a blackboard is the polynomial x2+x+2014x^{2} + x + 2014. Calvin and Hobbes take turns alternatively (starting with Calvin) in the following game. During his turn, Calvin should either increase or decrease the coefficient of xx by 11. And during his turn, Hobbes should either increase or decrease the constant coefficient by 11. Calvin wins if at any point of time the polynomial on the blackboard at that instant has integer roots. Prove that Calvin has a winning strategy.

Solution

Solution:

For i0i \geq 0, let fi(x)f_{i}(x) denote the polynomial on the blackboard after Hobbes' ii-th turn. We let Calvin decrease the coefficient of xx by 11. Therefore fi+1(2)=fi(2)1f_{i+1}(2) = f_{i}(2) - 1 or fi+1(2)=fi(2)3f_{i+1}(2) = f_{i}(2) - 3 (depending on whether Hobbes increases or decreases the constant term). So for some ii, we have 0fi(2)20 \leq f_{i}(2) \leq 2. If fi(2)=0f_{i}(2) = 0 then Calvin has won the game. If fi(2)=2f_{i}(2) = 2 then Calvin wins the game by reducing the coefficient of xx by 11. If fi(2)=1f_{i}(2) = 1 then fi+1(2)=0f_{i+1}(2) = 0 or fi+1(2)=2f_{i+1}(2) = -2. In the former case, Calvin has won the game and in the latter case Calvin wins the game by increasing the coefficient of xx by 11.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.