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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s