## Thoughts on a Problem II

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 $a_0$ of Q is obviously Q(10) mod 10, i.e. n mod 10, and the coefficient  $a_1$ of X is then given by $\frac{n - a_0}{10} \pmod{10}$ etc.

This does give us a hint on the uniqueness of Q in the original problem. Write the polynomial as $Q(X) = a_0 + a_1 X + a_2 X^2 + \dots + a_n X^n$.

• Since $n = Q(-2) \equiv a_0 \pmod 2$ and $n = Q(-5) \equiv a_0 \pmod 5$, we have $n \equiv a_0 \pmod {10}$. So $a_0$ is unique.
• For the next step, we need the constant term of $\frac{Q(X) - a_0}{X}$.
• Now we have $\frac {n - a_0}{-2} = \frac {Q(-2) - a_0}{-2}$ which is congruent to $a_1$ modulo 2.
• By the same token, $\frac{n - a_0}{-5} \equiv a_1 \pmod 5$.
• By Chinese Remainder Theorem, we thus get a unique solution for $a_1$.

So can we proceed by induction?

Suppose $a_0, a_1, \dots, a_k$ are unique. Then we need to prove that $a_{k+1}$, the constant term of $(Q(X) - a_0 - a_1 X - \dots - a_k X^k)/X^{k+1}$, is unique. Substituting Q(-2) = n and Q(-5) = n, we get:

$\frac{n - a_0 - a_1(-2) - \dots - a_k(-2)^k}{(-2)^{k+1}} \equiv a_{k+1} \pmod 2$, and $\frac{n - a_0 - a_1(-5) - \dots - a_k(-5)^k}{(-5)^{k+1}} \equiv a_{k+1} \pmod 5$ (*),

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 $a_0 \pmod {10}$ and subsequently every $a_{k+1}$ 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 $a_i = 0$ 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:

$b_{k} = n - a_0 - a_1(-2) - \dots a_k(-2)^k$ and $c_{k} = n - a_0 - a_1(-5) \dots - a_k(-5)^k$.

Thus, $a_{k+1} \equiv \frac{b_{k}}{(-2)^{k+1}} \pmod 2$ and $a_{k+1} \equiv \frac{c_{k}}{(-5)^{k+1}} \pmod 5$. We obtain the following.

• First step: $a_0 = 7$. OK.
• Step 2: $b_0 = n-7 = 50$ and $c_0 = 50$, so we have $a_1 \equiv \frac{b_0}{-2} = -25 \pmod 2$, $a_1 \equiv \frac{c_0}{-5} = -10 \pmod 5$. Thus $a_1 = 5$.
• Step 3: $b_1 = b_0 - 5(-2) = 60$ and $c_1 = c_0 - 5(-5) = 75$. So $a_2 \equiv \frac{b_1}{(-2)^2} = 15 \pmod 2$ and $a_2 \equiv \frac{c_1}{(-5)^2} = 3 \pmod 5$. Thus $a_2 = 3$.
• Step 4: $b_2 = b_1 - 3(-2)^2 = 48$ and $c_2 = c_1 - 3(-5)^2 = 0$. Hence $a_3 \equiv \frac{b_2}{(-2)^3} \pmod 2$ and $a_3 \equiv 0 \pmod 5$ and $a_3 = 0$.
• Step 5: $b_3 = b_2 = 48$ and $c_3 = c_2 = 0$ so we have $a_4 \equiv \frac{b_3}{(-2)^4} = 3 \pmod 2$ and $a_4 \equiv 0 \pmod 5$. This gives $a_4 = 5$.
• Step 6: $b_4 = b_3 - 5(-2)^4 = -32$ and $c_4 = c_3 - 5(-5)^4$ so $latex a_5 \equiv \frac{b_4}{(-2)^5} = -1 \pmod 2$ and $a_5 \equiv \frac{c_4}{(-5)^5} = 1 \pmod 5$. Thus $a_5 = 1$.
• Finally, $b_5 = c_5 = 0$. So we’re done.

The polynomial is hence Q(X) = 7 + 5X + 3X2 + 5X4 + X5. Notice that the ck series had hit zero by c2 but it bounces back later in c4 which shows that it (rather, its absolute value) is not a monotonic sequence.

But wait, we do know that $2^{k+1} | b_k$ and $5^{k+1} | c_k$, so actually, all we need is the fact that bk and ck are bounded sequences. So let’s try to bound them in terms of 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 a0 = n mod 10, $|\frac{n - a_0}{-2}| = \frac{n-a_0}2 < |n|$ (and same holds for (-5)-case) so induction follows.

But if n < 0? Then $|\frac{n - a_0}2| < |n|$ holds for sufficiently large |n|; specifically, n ≤ -10 suffices, for then we would have:

$|\frac{n-a_0}2| = \frac{a_0-n}2 < \frac{10-n}2 \le \frac{-n-n}2 = |n|$.

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

$Q(-2) = \frac{n - a_0}{-2}, \quad Q(-5) = \frac{n - a_0}{-5},$

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:

$(a_0, b_0) = (1, 0),\quad (a_{i+1}, b_{i+1}) = \left( \frac{a_i - t}{-2}, \frac{b_i - t}{-5}\right),$  (#)

for i = 0,1,2…, where t is the unique integer in {0,…,9} which is $\equiv a_i \pmod 2$ and $\equiv b_i \pmod 5$. 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 $5 + 6X + 6X^2 + 6X^3 + \dots$ 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 $|a_{i+1}| + |b_{i+1}| < |a_i| + |b_i|$ for all but finitely many $(a_i, b_i)$, 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 $a_{i+1} - b_{i+1} \equiv a_i - b_i \pmod 3$. So if we start from (n, n), we will always have $3 | (a_i - b_i)$, 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.

This entry was posted in Thought and tagged , , , , . Bookmark the permalink.