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\).

Infinite Internet !??

Quote from YouTube Video https://www.youtube.com/watch?v=YB-JItiQLF4 , "Researchers at MIT looked into it and concluded the amount of high quality data on the internet is finite"

Why did it require "researchers" at a prestigious institution to "look into" anything to discover this? This is akin to saying that Mathematicians have investigated boxes of corn flakes and concluded that most contain a finite number of flakes. Only a moron who did not know the meaning of "finite" and "non-finite" would have ever have thought otherwise (which suggest the quote comes from a press release produced by the public relations department at MIT). 

British Mathematical Olympiad 1993, Round 1 Question 1

Continuing with my current practice of finding mathematical problems to solve to keep  my mind occupied, my most recent foray has been a BMO1993-r1 problem:

Here I begin by assigning $B=\sqrt{n}$ and $A$ to be the three most significant digits of $n$. Then playing around we get:

$  n=B^2=1001\times A+1 $

Which suggests we rearrange this (a common manoeuvre for such problems) as:

$ B^2 -1=1001\times A $ 

 

$ (B+1)(B-1)=1001\times A $

Which tells us we want to rearrange the RHS of this last equation as the product of two integers that differ by $2$.  Also we can quickly eliminate the possibilities that the RHS is $1001\times 999$ and $1001\times 1002$ as one is not a square and the other has more than six digits.

That $B^2$ has six digits give constraints on possible values of $B$: $999\ge B \ge 317 $

The prime factorisation of $1001=7\times 11 \times 13$ and two of these factors must be factors of one of terms $(B+1)$ or $(B-1)$ and the remaining factor of the other term, so for some partition(s) $(p_1,p_2,p_3)$ of $(7,11,13)$ we may write:

$ (B+1)(B-1)=(p_1 \times p_2 \times U) \times (p_3 \times V) $

 where the first barracked term on the RHS differs from the second by $\pm 2$.

So lets take $p_1=7$ and $p_2=11$, then we have:

$ (B+1)(B-1)=(77 \times U) \times (13 \times V) $

Then for the $B$s to be in range $U$ is one of $5,6,7,8,9,10,11,12$ and $77$ times these are $385,462 ,539,616,693,770,847,924$.

For a solution we need one or more of these to differ from a multiple of $13$ by $\pm 2$. 

These are approximately $30,36,41,47,53,59,65,71$ $13$s or $390,468,533,611,689,767,845,923$.

We spot that the next to last of these differs from the next to last of the candidate for $U \times 77$ by $2$, and so provides a solution $B=846$, and $n=715716$.

There is no guarantee that this solution is unique, but then the question never asked for all, or a unique solution. Mechanising the heavy lifting give the fill list of solutions for $n$ as: $183184, 328329,528529,715716$.

Commentary on blog post on Putnam 1985/B-4

The solution to Putnam 1985/B-4 in another post on this blog illustrates something about real problem solving rather answers in exams/competitions. That is that for a real life problem a lot  of exploration/experimentation is undertaken before a formal solution/proof is developed. In fact for the problem in that other blog post there  was significantly more exploration involved in developing the ideas for a solution than is shown there. Mainly in the form of sketches of particular cases.

When results are published usually none of the exploratory work is mentioned. The solution/proof leaps fully formed like Athena from the head of Zeus. Probably the best known practitioner of extensive exploratory work hidden from the final publish result is Gauss.  

Putnam 1985 B-4 Problem

This is my rewording of question B-4 of the 1985 Putnam competition

A point $P1$, is uniformly sampled from the unit disc, and another $P2$, from the unit circle that is the boundary of the disc. What is the probability that the rectangle $R(P1,P2)$ with sides parallel to the axes and with these two points as opposite vertices  has points outside the disc.

Fig 1. Diagram showing a pair of points and the
rectangle the problem refers to.

Since we are not sitting in an exam room, nor am I going to look up the solution , and as usual when working on a problem all resources are deployed my first action when faced with a problem like this is to estimate the answer by simulation. That way I will have a check value when a more appropriate answer is found.

The first thing to observe is that if any points of the rectangle defined by $P1$ and $P2$ lie outside the unit disc then one of the other vertices of the rectangle must be outside the disc. This makes the simulation easier to implement as we need only check the other vertices.

The Gnu-Octave (Matlab clone-oid) simulation gives results:

Putnam1

number of replications = 100000

pp = 0.5971

se = 1.5510e-03

Where pp is the probability estimate, and se its standard error.

While we have a simulation available we might as well look at the scatter plot of points $P1$ that produce rectangles with points outside the disc... 

Fig 2. Scatter Plot of points P1 that result in a rectangle
with points outside the disc. The red marker indicates
position of P2 for this case.

The scatter plot suggests, what if I had been in training for the competition should have been obvious, that given $P2$ the points $P1$ outside the inscribed rectangle with $P2$ as a vertex will produce a rectangle $R(P1,P2)$ with points outside the unit disc.

So if $P2=(x,y)$ the area of the region is $A(P2)=2x\times 2y$. Or if we write $P2=(\cos(\theta),\sin(\theta))$ we get $A(P2)=4\cos(\theta).\sin(\theta)$.

Hence the probability that R(P2) has points outside the unit disc is 

$p(\theta)=(\pi-4 \cos(\theta) \sin(\theta))/ \pi$

Then the probability asked for in the question is:

$P=\frac{\int_0^{\pi/2} p(\theta) d\theta}{\pi/2} $

(the integral here only needs to extend over a quarter of the unit circle due to the symmetries of the geometry.

This integral is more or less text-book stuff, and can be done by using the double angle identity: $\sin(2\theta)=2 \sin(\theta).\cos(\theta)$ or observing that $\frac{d}{d\theta}\sin(\theta)=2 \sin(\theta).\cos(\theta)$.

Either way we find that:

$P= \left(\frac{\pi}{2}-\frac{2}{\pi}\right)/(\pi/2)\approx 0.5947$

The simulation  estimate is less than 2 standard errors from this, so these are sufficiently in agreement for government purposes.