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 October 2006 Problem

Problem:

x2 + 10 x + 20 into x2 + 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
x2 + 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 mission-impossible 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 x2 + (q+1)x + q for some integer q.  Unfortunately, x2 + (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 x2 + 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

 Math Central is supported by the University of Regina and the Pacific Institute for the Mathematical Sciences.
 about math central :: site map :: links :: notre site français