BMO 1993 R1 Q3

I have been working on the following problem from BMO 1993 round 1, question 3, somewhat unsuccessfully ... 

For each positive integer $c$ , the sequence $u_n$ of integers is defined by:

$u_1 = 1 , u_2 = c$, 

$u_n = (2 n +1) u_{n − 1} − ( n^2 − 1) u_{n − 2} , ( n ≥ 3)$. 

For which values of $c$ does this sequence have the property that $u_i$ divides $u_j$ whenever $i ≤ j$ ?

We can start by computing $u_3$ for general $c$, $u_3=7c-8$, then we are interested in values of $c$ which divide $7c-8$, which are $c=1,2,4,8$. We can test these candidates by computing the first few terms of the sequence.

For $c=1$ these are: $1,1,-1,-24,-240,-2280,..$, but $24\not{|}-2280$, so $c=1$ is not a permitted value.

For $c=2$ these are: $1,2,6,24,120,720..$, which all meet the divisibility condition, so we cannot eliminate $c=2$ as a permitted value.

For $c=4$ these are: $1,4,20,120,840,60480,..$, which all meet the divisibility condition, so we cannot eliminate $c=4$ as a permitted value.

For $c=8$ these are: $1,8,48,312,..$, but $48\not{|} 312$, so $c=8$ is not a permitted value.

So we are left with $c=2$ and $c=4$ as possible values.

At this point I thought maybe induction or descent might be up to completing this problem,  but after some effort(days) found I was getting nowhere, so decided to search for some help online. There I found a suggestion that the divisibility condition implies maybe factorials are involved. With this suggestion we recognise that for $c=2$ we have the sequence $1!,2!.3!,4!,5!,6!,...$, and that for $c=4$ we have the off set sequence of factorials divided by $6$. With these "guesses" for the sequences we can employ induction to prove that the required divisibility conditions are satisfied for every term, and so c=2 and c=4 are the values sought.

It would have been nice to have solved this without help, but at least we now know to try factorials when we have such divisibility requirements. I suppose I could have spotted that the sequence for $c=2$ was comprised of factorials, but I did not look at it closely enough.

Commentary on the solution of BMO 1993 Q2

 The basic idea behind finding the solution is simple: identify relevant variables, apply any constraints to find any relations between the variables, check boundary/edge cases then use calculus to find the value of the variable/s that minimise the length then use the value to find the minimum length.

Nothing exceptional here, in principle, though there is plenty of room for error in the fairly large amount of algebraic manipulation involved, until we get to the point of having to find real solutions to a quartic. Here we have to be able to spot that this is a special case of a quartic that can be solved without recourse to the quartic "formula".

Learning to spot such "nice" cases is one of the objectives of the training that MO competitors undergo. 

(I should point out that I have not had such training, and the idea of completing the fourth power came to me after several days of contemplation, in my sleep)

BMO 1993 Q2

 Q2. A square ABCD of side 1 is divided into two parts by the diagonal AC.

Find the length of the straight line, of minimum length,  that divides triangle ABC into two parts of equal area.

The first thing to do with this problem is to do a sketch and introduce some variables to characterise the approach to a solution. See the sketch below:

Diagram showing the construction and equation corresponding to the specified division of area.

Here I introduce variables \(a\) and \(b\) then the condition that the line cuts the area of the triangle into two equal area pieces gives:

\[A=\frac{a^2}{2}+a(1-a)+\frac{(b-a)(1-a)}{2}=\frac{1}{4}\]

Which may be rearranged to give \(b\) in terms of \(a\):

\[b=\frac{2a-1}{2a-2}\]

The length of the cut \({l}\) satisfies:

\[l^2=(b-a)^2+(1-a)^2\]

Then is we find \(a\) that miinimises \(l^2\) it also minimises \(l\), and this occurs when \(\frac{dl^2}{da}=0\).

After a lot of tedious algebra this gives:

\[\frac{dl^2}{da}=\frac{8a^4-32a^3+48a^2-32a+7}{2a^3-6a^2+6a-2}=0\]

Nowthe denominator is \(2(a-1)^2\) which is never zero on \( (0,1) \) and so can be multiplied out to leave:

\[8a^4-32a^3+48a^2-32a+7=0\]

Now we have the trixy part ... this is a quartic, and even though there is a "formula" for the roots of a quartic (Ferrari/Cardarno method) it is impractical to use in a exam setting (and I don't remember it anyway). But look at the coefficients of the non-constant terms, these are eight times the fourth row of Pascal's triangle, so:

\[8a^4-32a^3+48a^2-32a+7=8(a-1)^4+7-8=0\]

so if \(a\) is real: \((a-1)=\pm \frac{1}{2^{3/4}}\), or \(a=1-\frac{1}{2^{3/4}}\) (as we want the root between \(0\) and \(1\) ).

Then \(b=1-\frac{1}{2^{1/4}}\), and \(l=\sqrt{\sqrt{2}-1}\approx 0.6436\).