USAMO 97/A3 solution

26th USAMO 1997

Problem A3

Show that there is a unique polynomial whose coefficients are all single decimal digits which takes the value n at -2 and at -5.

Solution

Call the polynomial p(x) = p₀ + p₁x + p₂x² + ... + p_mx^m. Since p(x) - n = 0 has -2 and -5 as roots, it must have the factor (x + 2)(x + 5) = x² + 7x + 10. So for some a₀, a₁, a₂, ... we have:


10a₀              +n = p₀ ∈ {0,1,2,3,4,5,6,7,8,9}

10a₁ + 7a₀           = p₁ ∈ {0,1,2,3,4,5,6,7,8,9}

10a₂ + 7a₁ + a₀      = p₂ ∈ {0,1,2,3,4,5,6,7,8,9}

10a₃ + 7a₂ + a₁      = p₃ ∈ {0,1,2,3,4,5,6,7,8,9}

...

10a_r+1 + 7a_r + a_r-1  = p_r+1 ∈ {0,1,2,3,4,5,6,7,8,9}

...

Now these equations uniquely determine a_i and p_i. For p₀ must be chosen so that p₀ - n is a multiple of 10, which fixes p₀ and a₀ uniquely. Similarly, given p_i and a_i for 0 ≤ i ≤ r, we have p_r+1 = 10a_r+1 + 7a_r + a_r-1 = 7a_r + a_r-1 mod 10, so p_r+1 is uniquely determined and hence also a_r+1. Thus any solution is certainly unique, but it is not clear that the process terminates, so that p_i and a_i are zero from some point on.

Evidently the sequence a_i is bounded. For if a_i, a_i+1 ≤ B ≥ 9, then |a_i+2| ≤ 0.7B + 0.1B + 0.1B ≤ B. So if we take B = max(9,|a₀|,|a₁|), then |a_i| ≤ B for all i.

So we can define L_k = min(a_k, a_k+1, a_k+2, ...), U_k = max(a_k, a_k+1, a_k+2, ... ). Obviously, we have L₀ ≤ L₁ ≤ ... ≤ L_k ≤ L_k+1 ≤ ... ≤ U_k+1 ≤ U_k ≤ ... ≤ U₁ ≤ U₀. So L_i is an increasing integer sequence which is bounded above, so we must have L_i = L for all sufficiently large i. Similarly, U_i = U for all sufficiently large i, and L ≤ U (1).

But if a_i, a_i+1 ≥ L, then a_i+2 ≤ -0.7L - 0.1L + 0.9 ≤ -0.8L + 0.9. So U ≤ -0.8L + 0.9 (2). Similarly, if a_i, a_i+1 ≤ U, then a_i+2 ≥ -0.8U, so L ≥ -0.8U (3).

But as the diagram shows the only lattice point satisfying (1), (2), (3) is (0,0), so a_i = 0 for all sufficiently large i, which establishes existence.

26th USAMO 1997