Math Central - mathcentral.uregina.ca
Problem of the Month
 Currentproblem Recent problemswith solutions
 Older problems from 2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

Solution to April 2006 Problem

The Problem:
Two players take turns choosing a coefficient ai from the polynomial

x10 + a9 x9 + ... + a1 x + 1

and replacing it with an arbitrary real number. The game ends after 9 moves, when the values of all nine ai's have been selected. The first player to choose wins the game if the resulting polynomial has no real root, while the second player wins if the polynomial has at least one real root. One of the players has a winning strategy -- he wins no matter what his opponent does. Which player is it, and what is his winning strategy?

 Bojan Basic (Serbia and Montenegro) Matthew Lim (internet) Pierre Bornsztein (France) Patrick LoPresti (USA)

Solution.

The second player has the winning strategy.

Our four correspondents came up with similar strategies.  We reproduce here the Pierre Bornsztein's solution.

Among the nine coefficients of our given polynomial P(x) that are to be determined, five multiply the odd powers of x while four multiply the even powers.  If the first player, call him player A, chooses a coefficient of even index, the second player, call him B, should choose an odd index, and vice versa; B can give his coefficient any value he wishes.  He repeats the procedure for his second and third choices.  Thus after seven moves, when it is B's last turn, there remain two unchosen coefficients, call them ap and aq, with at least one of them, say p, odd.  Let Q(x) stand for the part of P(x) that is already determined by the first seven choices, so that at this stage,

P(x) = Q(x) + apxp + aqxq.

There are two cases to consider.

Case 1: q is even.

P(1)  = Q(1) + ap + aq

P(–1)  = Q(–1) – ap + aq

P(1) + P(–1)  = Q(1) + Q(–1) + 2aq.

Thus, if B assigns aq = –(½)(Q(1) + Q(–1)), then he is certain that P(1) + P(–1) = 0 no matter what value A assigns to ap.  Consequently, either P(1) = P(–1) = 0, or these two numbers have opposite signs.  In the former situation B wins because P(x) has a real root (in fact two: 1 and –1); in the latter, since polynomials are continuous for all x, the intermediate-value theorem insures that P will have a root between –1 and 1, so B wins whatever P(1) might be.

Case 2: q is also odd.

2q P(–1)  =  2q Q(–1) – 2q ap– 2q aq
P(2)   =  Q(2)   + 2p ap + 2q aq

2q P(–1) + P(2)  = 2q Q(–1) + Q(2) + (2p– 2q) ap.

Now if B assigns ap = (2q Q(–1) + Q(2))/(2q – 2p ), he is certain that 2q P(–1) + P(2) = 0 no matter what value A assigns to aq.  As before, either P(–1) and P(2) are both 0, or they have opposite signs.  Either way, B wins.

Thus we see that no matter what A does, B will win by following this procedure.