|
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?
We received correct solutions from
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.
Further comments.
We also received several other interesting contributions. Nikhil V. Nair (from India) considers a version of the game in which the players have to determine the coefficients a1, ..., a9 in order, and he shows that second player also has a winning strategy in this game. Philippe Fondanaiche (France) also provides a winning strategy for B, arguing that we may assume without loss of generality that player A, to maximize his chances, will favor the even coefficients a2, a4, a6, and a8, and give them positive values. Xavier Hecquet (France) shows that player A can force his opponent to work for his victory; he outlines a strategy for player A, decomposing P(x) into several polynomials that he tries to render all positive or zero by controlling various parameters
| 
