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 + 3X² + 5X⁴ + X⁵. Notice that the c_k series had hit zero by c₂ but it bounces back later in c₄ 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 b_k and c_k 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 a₀ = 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.

Thoughts on a Problem II

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Thoughts on a Problem II

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages