Re: Can someone explain this proof, please?

victor_meldrew_666@xxxxxxxxxxx wrote:

Timothy Murphy wrote:
Problem B1 (supposedly "easy" or even "trivial")
at the IMC (International Maths Competition) in 2001, in Prague, reads:

A URL

http://www.imc-math.org.uk/imc2001/prob_sol2.pdf

would have been useful to the reader.

In self-defence, I was actually given a printed copy
of the problem and solution at the IMC-2006 meeting,
and transcribed it myself.

a_i and b_j are non-negative reals such that

(a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} + x^n)
(b_0 + b_1x + b_2x^2 + ... + b_{m-1}x^{m-1} + x^m)
= 1 + x + x^2 + ... + x^{m+n}.

You have changed their r and s into n and m: later you use r and s :-(

True; sorry about that.

Show that all a_i and b_j are 0 or 1.

The solution offered reads (in toto):

Solution. Multiply the left hand side polynomials. We obtain the
following
equalities:
a0 b0 = 1, a0 b1 + a1 b0 = 1, . . .
Among them one can find equations
a0 + a1 bs-1 + a2 bs-2 + . . . = 1
and
b0 + b1 ar-1 + b2 ar-2 + . . . = 1.
From these equations it follows that a0 , b0 1.

Rather a_0, b_0 <= 1

Taking into account
that
a0 b0 = 1 we can see that a0 = b0 = 1.
Now looking at the following equations we notice that all a's must be
less
than or equal to 1. The same statement holds for the b's.

There are no "following equations". This is quite easy: comparing
coefficients of x^{i+m} gives
1 = a_i + nonnegative terms
so that a_i <= 1.

It follows from
a0 b1 + a1 b0 = 1 that one of the numbers a1 , b1 equals 0 while the
other one must
be 1. Follow by induction.

That last sentence is illiterate.

The proof offered was exactly as I gave it -
as you say, the English is not perfect.
I see that the proof at the URL you give,
<http://www.imc-math.org.uk/index.php?year=2001&item=problems>
is identical - word for word - to the one I gave.

It certainly does not follow from a_0 b_1 + a_1 b_0 = b_1 + a_1
(and the nonnegativity of a_1 and b_1) that one of a_1 and b_1 is zero.

There is an inductive proof. Take as induction hypothesis:
H_j: a_j = a_{n-j} in {0,1} and b_j = b_{n-j} in {0,1}.

I take it that should be b_j = b_{m-j} ?
Otherwise it is certainly not true for j = 0,
as if n < m then b_n = 0 from the coefficient of x^n
(while b_0 = 1).

Certainly H_0 is true. Assume j > 0 and H_i is true
whenever i < j.

If there is 0 < i < j with a_i b_{j-i} = 1 then by the x^j term
1 = a_j + b_j + a_i b_{j-1} + nonnegative terms

or rather, a_i b_{j-i}

so that a_j = b_j = 0.
Also a_{n-i} b_{m-j+i} = 1 and similarly a_{n-i} = b_{m-j+1} = 0.

I don't follow the last statement; similar to what?
I take it this is a (double) typo
and the argument should be:
the product above occurs in the coefficient of x^{m+n-j},
as also does a_n b_{m-j} = b_{m-j}
and a_{n-j} b_m = a_{n-j}.
Hence a_{n-j} = b_{m-j} = 0.

Otherwise (due to H_i and H_{j-i})
a_j b_{j-i} = 0 for all 0 < i < j which leads to

I take it this should be a_i b_{j-i}.
(Also I don't really see what H_i or H_{j-i} has to do with it.)

a_j + b_j = 1. In this case also a_{n-j} + b_{m-j} = 1.
If a_j > 0 then considering the x^m term gives
1 = 1 + a_j b_{m-j} + nonnegative terms
leading to b_{m-j} = 0. Similarly b_j > 0 implies a_{n-j} = 0.
As a_{n-j} + b_{m-j} = 1 at least one of a_j and b_j vanishes,
so one is 0 and the other 1. Similarly one of a_{n-j} and b_{n-j}
is 0 and the other 1. But a_j = 1 implies b_{m-j} = 0 implies
a_{n-j} = 1. Also b_j = 1 implies b_{n-j} = 1. We deduce
that always a_j = a_{n-j} and b_j = b_{m-j}.

Victor Meldrew

Thank you very much.
That is indeed a clever proof.

I think I must have been mistaken in believing that problem 1
was "easy" or even "trivial" in 2001 as it was in 2006!
This was the case in IMC-2006, where the questions ranged from
A1 and B1 trivial (all the contestants were expected to solve them)
to A6 and B6 "difficult".
(In fact any questions that could be solved by any of the 40 team leaders
in a 2-hour meeting were judged not to be hard enough.
IIRC, each of them was solved by one contestant.)

I assumed that this classification, easy to difficult,
had always been the case.
And the supplied "proof" certainly suggested
that the setter at least believed the problem was easily solved.


I take it that your proof shows that if the solution is written
f(x) g(x) = C(x),
then we get the same solution on replacing x by 1/x
ie (x^n f(1/x)) (x^m g(1/x)) = x^{m+n} C(1/x) = C(x).

Does this just follow on applying the conjugacy transformation
w -> w^{-1}, where w is the nth root of unity?
I'm not sure.



--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
.

Relevant Pages

  • Re: Israel Suspends Ties With Vatican
    ... Kind of like you believing a history book ... reliabilism is inductive, but then so is another justification system ... Induction is believing the book in general or a kind of book in general ...
    (soc.culture.jewish.moderated)
  • Re: FACTORIALS BY Algorithm -please comment
    ... Then notice that P-Pis a polynomial of degree n-1, ... coefficient of x^is n*a. ... Using the above fact and induction, you can see that you will end up ... "Finite Differences" ...
    (sci.math)