Note: More than one option maybe correct.

Alice and Bob are playing a game. At the beginning of the game, there is a cubic polynomial with integral coefficients written on the blackboard, which we denote as the starting polynomial. The two players take turns one by one. In each turn, the player either chooses any natural number $n$ and replaces the existing cubic polynomial $f(x)$ on the blackboard by any one of $f(n + x), f(nx), f(x) + n$ or just changes the sign of the coefficients of $x^2$ , i.e. if the existing polynomial is $a_0 + a_1x + a_2x^2 + a_3x^3$, then he can replace it by $a_0 + a_1x - a_2x^2 + a_3x^3$. Alice takes the first turn. Bob wins if, after finitely many moves, the cubic polynomial on the blackboard has all coefficients (upto $x^3$) non-zero and equal. For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?

a) $x^3+4x^2+4x+1$

b) $x^3+6x^2+7x$

c) $x^3+3$

d) none of the above

It is an art of problem-solving question and I am not getting any clue. Please help how to solve these problems.

  • $\begingroup$ If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$? $\endgroup$ – Lincon Ribeiro Jan 10 at 21:18
  • $\begingroup$ @LinconRibeiro: that was one of the options for the players, to negate the quadratic term. $\endgroup$ – Ross Millikan Jan 10 at 21:27
  • $\begingroup$ Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting. $\endgroup$ – Ross Millikan Jan 10 at 21:53
  • $\begingroup$ Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link. $\endgroup$ – Gimgim Jan 10 at 21:54

Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d \gt a$ and the ratio $\frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.

The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.

The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.

  • $\begingroup$ Hi, Will you please explain with one of the example say for the polynomial a)? $\endgroup$ – Gimgim Jan 10 at 21:53
  • 1
    $\begingroup$ Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d \gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these. $\endgroup$ – Ross Millikan Jan 10 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.