Solution to October 2006 Problem
Problem:
Your task is to convert
x^{2} + 10 x + 20 into x^{2} + 20 x + 10
in 50 steps or less, where on each step you are allowed
to add 1 to, or to subtract 1 from, either the current constant term or the coefficient of x (but not both),
subject to the condition that
no change is allowed to produce a polynomial that can be factored into
(x + m)( x + n), where m and n are integers.
For example, the first step cannot reduce the 10 to 9 because
x^{2} + 9 x + 20 = (x + 5)(x + 4).
ACKNOWLEDGMENT. Our October problem was taken from Edward J. Barbeau, Polynomials (Springer, 1989), page 41 #6.
We received correct solutions from
Mario Antunez (Honduras) 

Wolfgang Kais (Germany) 
Quinn Barber (Alberta) 

Matthew Lim (USA) 
Pierre Bornsztein (France) 

Patrick LoPresti (USA) 
Bernard Carpentier (France) 

Juan Mir Pieras (Spain) 
K.A. Chandrashekara (India) 

Wilfrid Pillard (France) 
Sébastien Dumortier (France) 

Torin Stepan (Alberta) 
Philippe Fondanaiche (France) 

A. Teitelmam (Israel) 
Xavier Hecquet (France) 


Solution.
Fondanaiche suggested we turn the task over to Sisyphus to keep him busy when he tires of rolling his stone up the hill. A few correspondents referred to their task as "Mission Impossible"! But, of course, the missionimpossible team always manages to accomplish their mission. Here even the great Tom Cruise would fail. It can't be done, even if we allow extra steps. There were two basic approaches.
The algebraic solution. (This version is based on similar solutions from Bornsztein, Carpentier, Fondanaiche, and Kais.)
Let p be the current coefficient of x and q the constant term, and consider their difference d = p – q. On each step d changes by +1 or by –1. At the start d = –10, while at the finish d must equal +10. Therefore, somewhere along the way this difference would take a value of 1. The resulting polynomial would then be x^{2} + (q+1)x + q for some integer q. Unfortunately, x^{2} + (q+1)x + q = (x + q)(x + 1) with q and 1 integers, which is not allowed.
The geometric solution. (This version comes mostly from Mir, with ideas from other similar solutions.)
We can assign the polynomial x^{2} + px + q to the square with coordinates (p, q) in an infinite chessboard. At each step we move one square right or left, up or down (but not diagonally). Colour each square red that corresponds to a polynomial that can be factored into (x + m)(x + n) where m and n are integers. Our task is to move from the square (10, 20) to the square (20, 10) one step at a time without entering a red square. This can never be done because there is a full red diagonal (q+1, q) between those two squares.
Dumortier, Chandrashekara, and Hecquet each attached a picture that shows a portion of the chessboard. Dumortier's picture shown below indicates squares that correspond to factorable polynomials by 0 and colours them red; for polynomials that are irreducible over the integers he marks the corresponding square 1 and colours it blue.
click image to enlarge