Problem: (2002 MOP Homework - #7) Peter and Alex play a game starting with an ordered pair $ (a,b) $. On each turn, the current player increases or decreases either $ a $ or $ b $: Peter by $ 1 $, Alex by $ 1 $ or $ 3 $. Alex wins if at some point in the game the roots of $ x^2+ax+b $ are integers. Is it true that given any initial values of $ a $ and $ b $, Alex can guarantee that he wins?
Solution: We claim that Alex can guarantee that he wins for any initial values of $ a $ and $ b $. Call an ordered pair $ (a,b) $ "good" if Alex can win regardless of who starts.
We claim that if $ (a,b) $ is good, then $ (-a,b) $ is good as well. This is clear because $ (a,b) $ is good implies that $ x^2+ax+b = (x-r_1)(x-r_2) $ for integers $ r_1, r_2 $. Then $ x^2-ax+b = (x+r_1)(x+r_2) $ which also has integer roots. So it is sufficient to show that $ (a,b) $ is good for all $ a $ and $ b $ with the same sign.
First, we will show that if $ |a| \le 1 $ and $ |b| \le 1 $, then $ (a,b) $ is good.
Case 1. $ (0,0) $: $ x^2 $ has integer root $ 0 $. It is good.
Case 2. $ (1,0) $: $ x^2+x $ has integer roots $ 0, -1 $. It is good.
Case 3. $ (-1,0) $: $ x^2-x $ has integer roots $ 0, 1 $. It is good.
Case 4. $ (0,-1 $: $ x^2-1 $ has integer roots $ -1, 1 $. It is good.
Case 5. $ (0,1) $: $ x^2+1 $. If Peter starts, he must change $ b $ or Alex will decrease $ b $ to zero and the roots will be integral. But if he decreases $ b $, it becomes the same as Case 1, and if he increases it, Alex can decrease by $ 3 $ and it will become the same as Case 4. If Alex starts, he can decrease $ b $ by $ 1 $ to get Case 1. So it is good.
Case 6. $ (1,-1) $: $ x^2+x-1 $. If Peter starts, decreasing $ a $ or increasing $ b $ will result in Cases 4 and 2, respectively. If he does not change $ b $, Alex can increase $ b $ by $ 1 $ to get integer roots. And if he decreases $ b $ then $ x^2+x-2 $ has roots $ -2, 1 $. If Alex starts, he can increase $ b $ by $ 1 $ to get integer roots. So it is good.
Case 7. $ (1,1) $: $ x^2+x+1 $. If Peter starts, decreasing either $ a $ or $ b $ will reduce it to Cases 5 and 2, respectively. So he must increase one of them. If he increases $ a $, $ x^2+2x+1 $ has root $ -1 $, and if he increases $ b $, Alex may decrease $ b $ by $ 3 $ to get Case 6. So it is good.
Case 8. $ (-1,-1) $: $ x^2-x-1 $. Follows from Case 6. It is good.
Case 9: $ (-1,1) $: $ x^2-x+1 $. Follows from Case 7. It is good.
We claim that if the ordered pairs $ (x,y) $ for $ x,y \in \{0,1,2,\cdots,m\} $ (with $ m \ge 1 $) are good, then the ordered pairs containing $ m+1 $ are good as well. If this is true, then all ordered pairs $ (a,b) $ with $ a,b $ nonnegative are good. We will proceed by induction.
Base Case - We know $ (0,0) $, $ (0,1) $, $ (1,0) $, and $ (1,1) $ are good.
Induction Step - We have $ (x,y) $ for $ x,y \in \{0,1,2,\cdots,m\} $ good.
Take any ordered pair $ (m+1,n) $ or $ (n,m+1) $ for $ n \in \{0,1,2,\ldots,m\} $. If Peter goes first, then he must make one of the variables not be a member of the set $ \{0,1,2,\ldots,m\} $. But Alex can change it by either $ 1 $ or $ 3 $ such that it becomes a member of the set again (since the set has size at least $ 2 $). Then the case $ (m+1,m+1) $ can be reduced to one of the previous cases as well. If Alex goes first, he can also reduce it to $ (m,n) $ and then it's the same as if Peter went first with the ordered pair $ (m,n) $. This completes the induction.
Similarly, we can do this for all ordered pairs of negative numbers and show that they are good, and by an above claim all ordered pairs with integers of opposite sign are good as well. Hence all ordered pairs are good as desired. QED.
--------------------
Comment: There's probably a more straightforward solution to this problem, but basing it off an induction worked pretty well, because it's easy for Alex to reduce any ordered pair to a smaller one, hence the idea for induction.
--------------------
Practice Problem: Suppose Alex could only increase/decrease by $ 1 $ and $ 4 $. Can he still always win?
No comments:
Post a Comment