The following problem caught my eye:

(USAMO 1997 Q3) Prove that for any integer n, there is a unique polynomial Q(X) whose coefficients all lie in the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and Q(-2) = Q(-5) = n.

Notice that this bears a strong resemblance to decimal representation: for any non-negative integer *n*, there is a unique polynomial *Q*(*X*) whose coefficients are in the above set and *Q*(10) = *n*. The proof of this one is quite obvious: the constant term of *Q* is obviously *Q*(10) mod 10, i.e. *n* mod 10, and the coefficient of *X* is then given by etc.

This does give us a hint on the uniqueness of *Q* in the original problem. Write the polynomial as .

- Since and , we have . So is unique.
- For the next step, we need the constant term of .
- Now we have which is congruent to modulo 2.
- By the same token, .
- By Chinese Remainder Theorem, we thus get a unique solution for .

So can we proceed by induction?

Suppose are unique. Then we need to prove that , the constant term of , is unique. Substituting *Q*(-2) = *n* and *Q*(-5) = *n*, we get:

, and (*),

which completes the induction. So uniqueness is done.

Existence seems to follow via the same proof also, which is clearly constructive. The constant term is given by and subsequently every is determined uniquely from the two congruences in (*). The only problem is to show that the process must terminate, i.e. that eventually we get for all *i* > *N*. [ In mathematical lingo, we say “for all large enough *i*“. ]

To get a handle on things, let’s work on something concrete, say: 26 + 31 = 57. [ SIMO people should know the significance of these numbers. 🙂 ]

To avoid cumbersome terms, we write the differences:

and .

Thus, and . We obtain the following.

- First step: . OK.
- Step 2: and , so we have , . Thus .
- Step 3: and . So and . Thus .
- Step 4: and . Hence and and .
- Step 5: and so we have and . This gives .
- Step 6: and so $latex a_5 \equiv \frac{b_4}{(-2)^5} = -1 \pmod 2$ and . Thus .
- Finally, . So we’re done.

The polynomial is hence *Q*(*X*) = 7 + 5*X* + 3*X*^{2} + 5*X*^{4} + *X*^{5}. Notice that the *c _{k}* series had hit zero by

*c*

_{2}but it bounces back later in

*c*

_{4}which shows that it (rather, its absolute value) is not a monotonic sequence.

But wait, we do know that and , so actually, all we need is the fact that *b _{k}* and

*c*are bounded sequences. So let’s try to bound them in terms of

_{k}*n*. In attempting to prove this, we’ve to be careful. Note that if we had replaced -2 and -5 by +2 and +5 respectively, the result clearly doesn’t hold for negative integers.

*So our proof must somehow distinguish between these 2 cases*.

… or have we been looking at the wrong approach? Maybe let’s prove existence of *Q* via induction on |*n*|? So suppose for each |*n*|<*N*, there exists a *Q* as above. If *n* > 0, then since *a*_{0} = *n* mod 10, (and same holds for (-5)-case) so induction follows.

But if *n* < 0? Then holds for sufficiently large |*n*|; specifically, *n* ≤ -10 suffices, for then we would have:

.

Same holds for (-5)-case. So all we need to do is to provide explicit polynomials for the case where *n*=-1, …, -9. But… something feels amiss: somehow the induction doesn’t quite carry through, for to get to the next stage of induction, we need to find a polynomial *Q*(*X*) such that

which cannot be deduced from induction hypothesis. So let’s try to generalise the above result: maybe it’s true that for any pair of integers (*a*, *b*) there exists a polynomial *Q*(*X*) with coefficients in {0,…,9} such that *Q*(-2) = *a*, *Q*(-5) = *b*?

But that turns out to be wrong! E.g. no such polynomial exists for (*a*, *b*) = (1, 0). If we try to recursively define the polynomial coefficients, we get:

(#)

for *i* = 0,1,2…, where *t* is the unique integer in {0,…,9} which is and . The sequence of *t*‘s then gives the coefficients. For the starting value of (1, 0), we get (1, 0) → (2, 1) → (2, 1) → (2, 1) … . So we get an infinite power series rather than a polynomial!

In short, if we start with an arbitrary integer pair (*a*, *b*) and recursively define (#), not all sequence would end up at (0, 0). But in particular, we’re supposed to show (*n*, *n*) does. How do we do that?

We look at all possible end-cycles for the sequence (#). Since for all but finitely many , we can list them all out. The only possibilities are:

- (0, 0) → (0, 0) → … (the nice case);
- (2, 1) → (2, 1) → (2, 1) → … ;
- (3, 1) → (-1, 0) → (3, 1) → (-1, 0) → … .

We have to show that the recurrence relation starting from (*n*, *n*) will never end up in the second or third case.

Embarrassingly, it took me quite a while to see the trick: modulo 3. From the recurrence relation (#), we see that . So if we start from (*n*, *n*), we will always have , while for the second and third case, we have *a* – *b* ≡ 1, 2 (mod 3) respectively.

That completes the proof. But now the task is to express it in a rigourous manner, which we’ll leave to the reader.