Intel Pentium P5 floating point unit error (1994) — an RMO problem !!!

Problem:

Two number theorists, bored in a chemistry lab, played a game with a large flask containing 2 litres of a colourful chemical solution and an ultra-accurate pipette. The game was that they would take turns to recall a prime number p such that p+2 is also a prime number. Then, the first number theorist would pipette out 1/p litres of chemical and the second \frac{1}{(p+2)} litres. How many times do they have to play this game to empty the flask completely?

Hint:

A bit of real analysis is required.

Reference:

I will publish the reference when I post the solution. So that all students/readers can curb their impulse to see the solution immediately!!!

I hope you will be hooked to the problem in a second….!!! Here is a beautiful utility of pure math! 🙂

Cheers,

Nalin Pithwa

PS: I do not know if the above problem did (or, will?? )appear as RMO question. It is just my wild fun with math to kindle the intellect of students in analysis !! 🙂

Huygens’ problem to Leibnitz: solution

In the Feb 23 2018 blog problem, we posed the following question:

Sum the following infinite series:

1+\frac{1}{3} + \frac{1}{6} + \frac{1}{10} + \frac{1}{15}+ \ldots.

Solution:

The sum can be written as:

S=\sum_{n=1}^{\infty}P_{n}, where P_{n}=\frac{2}{n(n+1)}=2(\frac{1}{n}-\frac{1}{n+1}).

Thus, 2(1-\frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \frac{1}{3} - \frac{1}{4} + \ldots)=2. This is the answer.

If you think deeper, this needs some discussion about rearrangements of infinite series also. For the time, we consider it outside our scope.

Cheers,

Nalin Pithwa.

Real Numbers, Sequences and Series: part 9

Definition.

We call a sequence (a_{n})_{n=1}^{\infty} a Cauchy sequence if for all \varepsilon >0 there exists an n_{0} such that |a_{m}-a_{n}|<\varepsilon for all m, n > n_{0}.

Theorem:

Every Cauchy sequence is a bounded sequence and is convergent.

Proof.

By definition, for all \varepsilon >0 there is an n_{0} such that

|a_{m}-a_{n}|<\varepsilon for all m, n>n_{0}.

So, in particular, |a_{n_{0}}-a_{n}|<\varepsilon for all n > n_{0}, that is,

a_{n_{0}+1}-\varepsilon<a_{n}<a_{n_{0}+1}+\varepsilon for all n>n_{0}.

Let M=\max \{ a_{1}, \ldots, a_{n_{0}}, a_{n_{0}+1}+\varepsilon\} and m=\min \{ a_{1}, \ldots, a_{n_{0}+1}-\varepsilon\}.

It is clear that m \leq a_{n} \leq M, for all n \geq 1.

We now prove that such a sequence is convergent. Let \overline {\lim} a_{n}=L and \underline{\lim}a_{n}=l. Since any Cauchy sequence is bounded,

-\infty < l \leq L < \infty.

But since (a_{n})_{n=1}^{\infty} is Cauchy, for every \varepsilon >0 there is an n_{0}=n_{0}(\varepsilon) such that

a_{n_{0}+1}-\varepsilon<a_{n}<a_{n_{0}+1}+\varepsilon for all n>n_{0}.

which implies that a_{n_{0}+1}-\varepsilon \leq \underline{\lim}a_{n} =l \leq \overline{\lim}a_{n}=L \leq a_{n_{0}+1}+\varepsilon. Thus, L-l \leq 2\varepsilon for all \varepsilon>0. This is possible only if L=l.

QED.

Thus, we have established that the Cauchy criterion is both a necessary and sufficient criterion of convergence of a sequence. We state a few more results without proofs (exercises).

Theorem:

For sequences (a_{n})_{n=1}^{\infty} and (b_{n})_{n=1}^{\infty}.

(i) If l \leq a_{n} \leq b_{n} and \lim_{n \rightarrow \infty}b_{n}=l, then (a_{n})_{n=1}^{\infty} too is convergent and \lim_{n \rightarrow \infty}a_{n}=l.

(ii) If a_{n} \leq b_{n}, then \overline{\lim}a_{n} \leq \overline{\lim}b_{n}, \underline{\lim}a_{n} \leq \underline{\lim}b_{n}.

(iii) \underline{\lim}(a_{n}+b_{n}) \geq \underline{\lim}a_{n}+\underline{\lim}b_{n}

(iv) \overline{\lim}(a_{n}+b_{n}) \leq \overline{\lim}{a_{n}}+ \overline{\lim}{b_{n}}

(v) If (a_{n})_{n=1}^{\infty} and (b_{n})_{n=1}^{\infty} are both convergent, then (a_{n}+b_{n})_{n=1}^{\infty}, (a_{n}-b_{n})_{n=1}^{\infty}, and (a_{n}b_{n})_{n=1}^{\infty} are convergent and we have \lim(a_{n} \pm b_{n})=\lim{(a_{n} \pm b_{n})}=\lim{a_{n}} \pm \lim{b_{n}}, and \lim{a_{n}b_{n}}=\lim {a_{n}}\leq \lim {b_{n}}.

(vi) If (a_{n})_{n=1}^{\infty}, (b_{n})_{n=1}^{\infty} are convergent and \lim_{n \rightarrow \infty}b_{n}=l \neq 0, then (\frac{a_{n}}{b_{n}})_{n=1}^{\infty} is convergent and \lim_{n \rightarrow \frac{a_{n}}{b_{n}}}= \frac{\lim {a_{n}}}{\lim{b_{n}}}.

Reference: Understanding Mathematics by Sinha, Karandikar et al. I have used this reference for all the previous articles on series and sequences.

More later,

Nalin Pithwa

 

Sequences of integers

Sequences of integers are a favourite of olympiad problem writers since such sequences involve several different mathematical concepts, including for example, algebraic techniques, recursive relations, divisibility and primality.

Problem:

Consider the sequence (a_{n})_{n \geq 1} defined by a_{1}=a_{2}=1a_{3}=199 and

a_{n+1}=\frac{1989+a_{n}a_{n-1}}{a_{n-2}} for all n \geq 3. Prove that all the terms of the sequence are positive integers.

Solution:

There is no magic or sure shot or short cut formula to such problems. All I say is the more you read, the more rich your imagination, the more you try to solve on your own.

We have a_{n+1}a_{n-2}=1989+a_{n}a_{n-1}

Replacing n by n-1 yields, a_{n}a_{n-3}=1989+a_{n-1}a_{n-2} and we obtain

a_{n+1}a_{n-2} - a_{n}a_{n-1}=a_{n}a_{n-3}-a_{n-1}a_{n-2}

This is equivalent to

a_{n-2}(a_{n+1}+a_{n-1})=a_{n}(a_{n-1}+a_{n-3})

or \frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}} for all n \geq 4. If n is even, we obtain

\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}= \ldots = \frac{a_{3}+a_{1}}{a_{2}}=200

while if n is odd,

\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}=\ldots=\frac{a_{4}+a_{2}}{a_{3}}=11

It follows that a_{n+1} = 200a_{n}-a_{n-1}, if n is even,

and a_{n+1}=11a_{n}-a_{n-1}, if n is odd.

An inductive argument shows that all a_{n} are positive integers.

More later,

Nalin Pithwa

Real Numbers, Sequences and Series: Part 6

Theorem:

Given x \in \Re_{+} and n \in N, we can find y \in \Re such that x=y^{n}.

Proof:

Let A={u \in \Re_{+}: u^{n}<x}. If x<1, then x^{n} <x and hence x \in A. On the other hand, if x \geq 1, then 1/2 \in A. Thus, A is non-empty. Next, observe that if v^{n}>x, then v is an upper bound of A. In particular, \{ 1+x\} is an upper bound of A.

By the least upper bound property, A admits a least upper bound. Let us denote it by y. We will rule out the possibilities y^{n}>x and y^{n}<x implying that x=y^{n}.

If y^{n}<x, let a=\frac{x-y^{n}}{nx} and z=y(1+a). It can be checked that z^{n}<x so that z \in A. But, y <x, contradicting the fact that y is the least upper bound of A. (we have used the inequalities 7 and 8 in the previous blog).

On the other hand, if y^{n}>x, let \frac{y^{n}-x}{ny^{n}} and w=y(1-b). Again, it can be verified that w^{n}>x and hence w is an upper bound of A. But, w<y, contradicting the fact that y is the least upper bound of A. Hence, y^{n}=xQED.

In particular, we see that there is an element \alpha \in \Re such that \alpha^{2}=2 and hence also (-\alpha)^{2}=2 which means that the equation x^{2}=2 has two solutions. The positive one of those two solutions is \sqrt{2}. In fact, the above theorem has guaranteed its extraction of the square root, cube root, even nth root of any positive number. You could ask at this stage, if this guarantees us extraction of square root of a negative number. The answer is clearly no. Indeed, we have

x^{2} \geq 0 for x \in \Re.

Remark.

We can further extend \Re to include numbers whose squares are negative, which you know leads to the idea of complex numbers.

We have shown that Q is a subset of \Re. One can also show that between any two distinct real numbers there is a rational number. This naturally leads to the decimal representation of real number: Given any real number x and any q \in N, we can get a unique a_{0} \in Z and unique a_{1},a_{2}, \ldots a_{q} \in N such that 0 \leq a_{1} \leq a_{2} \ldots a_{q} \leq 9 and

|x-(a_{0}+a_{1}/10+a_{2}/100+\ldots + \frac{a_{q}}{10^{q}})|<\frac{1}{10^{q}}

You are invited to try to  prove this familiar decimal representation.

If we have a terminating decimal representation of a real number, then surely it is rational.But, we know that rationals like 1/3, 1/7, 1/11, do not have a terminating decimal expansion.

It is clear that the decimal representation of \sqrt{2} cannot terminate as it is not rational. There are many elements of \Re which are not in Q. Any element of \Re which is not in is called an irrational number, and irrational numbers cannot have terminating decimal representation.

More later,

Nalin Pithwa

Real numbers, sequences and limits: part IV

Representation of Q on the Number Line.

We have seen earlier that every element of can be represented on a straight line with a certain point representing 0. Positive integers are represented by points to the right of this marked point at equal lengths, and negative integers are similarly represented by points to the left of this.

We can use the same straight line to represent the newly constructed rational numbers as follows.

We know that we can divide a line segment, using a straight edge and compass, into q equal parts. So, the line segment between 0 to 1 can be divided into q equal parts for every positive integer q.

The points of division will now represent the numbers \frac{1}{q}, \frac{2}{q}, \ldots , \frac{q-1}{q}. It is now clear that any rational number of the form \frac{p}{q} can be represented on the straight line. We have seen that between any two distinct rational numbers r and r^{'}, no matter how close they are, we can always find another rational number between them, example, \frac{r+r^{"}}{2}. Geometrically, this means that between any two distinct points on the line representing rational numbers, there is a point between them representing a rational number.

One can ask: does every point on the line correspond to a rational number? Note that we also have a point on the line representing length of the diagonal of a square of side 1. But, we shall show in the next blog that the length of the diagonal of unit square does not correspond to a rational number.

To prepare the ground for such discussions, let us start with a few definitions:

A subset A \subset Q is said to be bounded below if there exists a rational number \alpha such that

\alpha \leq \beta for every \beta \in A

and \alpha is called a lower bound of A. Similarly, A \subset Q is said to be bounded above if there is a \gamma \in Q such that \beta \leq \gamma, and \gamma is called an upper bound of A. A set which is bounded above and also bounded below is called a bounded set. Observe that if a set has a lower bound \alpha then it has many more like \alpha -1, \alpha -2, \ldots. Similarly, a set that is bounded above has many upper bounds. If there is a least element of all these upper bounds, then we call it the least upper bound of the set. But, it is not true that every set of rational numbers which is bounded above has a least upper bound. We can say similar things about sets which are bounded below. Some sets may have least upper bound. For example, the set of negative rational numbers is certainly bounded above and it is easy to see that 0 is the least upper bound.

More later,

Nalin Pithwa