## Category Archives: IITJEE Advanced Mathematics

### Maxima and minima — using calculus — for IITJEE Advanced Mathematics

Problem:

The length of the edge of the cube $ABCDA_{1}B_{1}C_{1}D_{1}$ is 1. Two points M and N move along the line segments AB and $A_{1}D_{1}$, respectively, in such a way that at any time t $(0 \leq t < \infty)$ we have $BM = |\sin{t}|$ and $D_{1}N=|\sin(\sqrt{2}t)|$. Show that MN has no maximum.

Proof:

Clearly, $MN \geq MA_{1} \geq AA_{1} =1$. If $MN=1$ for some t, then $M=A$ and $N=A_{1}$, which is equivalent to $|\sin{t}|=1$ and $|\sin{\sqrt{2}t}|=1$. Consequently, $t=\frac{\pi}{2}+k\pi$ and $\sqrt{2}t=\frac{\pi}{2}+n\pi$ for some integers k and n, which implies $\sqrt{2}=\frac{2n+1}{2k+1}$, a contradiction since $\sqrt{2}$ is irrational. This is why $MN >1$ for any t.

We will now show that MN can be made arbitrarily close to 1. For any integer k, set $t_{k}=\frac{\pi}{2}+k\pi$. Then, $|\sin{t_{k}}|=1$, so at any time $t_{k}$, the point M is at A. To show that N can be arbitrarily close to $A_{1}$ at times $t_{k}$, it is enough to show that $|\sin(\sqrt{2}t_{k})|$ can be arbitrarily close to 1 for appropriate choices of k.

We are now going to use Kronecker’s theorem:

If $\alpha$ is an irrational number, then the set of numbers of the form $ma+n$where m is a positive integer while n is an arbitrary integer, is dense in the set of all real numbers. The latter means that every non-empty open interval (regardless of how small it is) contains a number of the form $ma+n$.

Since $\sqrt{2}$ is irrational, we can use Kronecker’s theorem with $\alpha=\sqrt{2}$. Then, for $x=\frac{1-\sqrt{2}}{2}$, and any $\delta>0$, there exist integer $k \geq 1$ and $n_{k}$ such  that $k\sqrt{2}-n_{k} \in (x-\delta, x+\delta)$. That is, for $\in_{k}=\sqrt{2}k+\frac{\sqrt{2}}{2}-\frac{1}{2}-n_{k}$ we have $|\in_{k}|<\delta$. Since $\sqrt{2}(k+\frac{1}{2})=\frac{1}{2}+n_{k}+\in_{k}$, we have

$|\sin(\sqrt{2}t_{k})|=|\sin \pi \sqrt{2}(k+\frac{1}{2})|=|\sin(\frac{\pi}{2}+n_{k}\pi+\in_{k}\pi)|=|\cos{(\pi \in_{k})}|$.

It remains to note that $|\cos{(\delta\pi)}|$ tends to 1 as $\delta$ tends to 0.

Hence, MN can be made arbitrarily close to 1.

Ref: Geometric Problems on Maxima and Minima by Titu Andreescu, Oleg Mushkarov, and Luchezar Stoyanov.

Thanks to Prof Andreescu, et al !

Nalin Pithwa

Ref: Titu Andreescu and Zumin Feng.

Problem:

Let x, y, z be positive real numbers such that $x+y+z=1$. Determine the minimum value of

$\frac{1}{x}+\frac{4}{y}+\frac{9}{z}$

Solution:

An application of CauchySchwarz inequality makes this as a one step problem. Nevertheless, we present a proof which involves only the easier inequality $x^{2}+y^{2} \geq 2xy$ for real numbers x and y by setting first $x=\tan {b}$ and $y=2\tan{b}$ and second $x=\tan{a}$ and $y=\cot{a}$.

Clearly, z is a real number in the interval $[0,1]$. Hence, there is an angle a such that $z=\sin^{2} {a}$. Then, $x+y=1-\sin^{2}{a}=\cos^{2}{a}$, or $\frac{x}{\cos^{2}{a}}+\frac{y}{\cos^{2}{a}}=1$. For an angle b, we have $\cos^{2}{b}+\sin^{2}{b}=1$. Hence, we can set $x=\cos^{2}{a}\cos^{2}{b}$, and $y=\cos^{2}{a}\sin^{2}{b}$ for some b, it suffices to find the minimum value of

$P = \sec^{2}{a} \sec^{2}{b}+4\sec^{2}{a}\csc^{2}{b}+9\csc^{2}{a}$

or

$P = (\tan^{2}{a}+1)(\tan^{2}{b}+1)+4(\tan^{2}{a}+1)(\cot^{2}{b}+1)+9(\cot^{2}{a}+1)$

Expanding the right hand side gives

$P = 14 + 5\tan^{2}{a}+9\cot^{2}{a}+(\tan^{2}{b}+4\cot^{b})(1+\tan^{2}{a})$

$\geq 14 + 5\tan^{2}{a}+9\cot^{2}{a}+2\tan{b}.2\cot{b}(1+\tan^{2}{a})$

$= 18 + 9(\tan^{2}{a}+\cot^{2}{a}) \geq 18 + 9.2\tan{a}\cot{a}=36$

Equality holds when $\tan{a}=\cot{a}$ and $\tan{b}=2\cot{b}$, which implies that $\cos^{2}{a}=\sin^{2}{a}$ and $2\cos^{2}{b}=\sin^{b}$. Because $\sin^{2}{\theta}+\cos^{2}{\theta}=1$, equality holds when $\cos^{2}{a}=\frac{1}{2}$ and $\cos^{2}{b}=\frac{1}{3}$, that is, $x=\frac{1}{6}$, $y=\frac{1}{3}$, $z=\frac{1}{2}$.

More later.

Nalin Pithwa

### Inclusion Exclusion Principle theorem and examples

Reference: Combinatorial Techniques by Sharad Sane, Hindustan Book Agency.

Theorem:

The inclusion-exclusion principle: Let X be a finite set and let and let $P_{i}: i = 1, 2, \ldots n$  be a set of n properties satisfied by (s0me of) the elements of X. Let $A_{i}$ denote the set of those elements of X that satisfy the property $P_{i}$ . Then, the size of the set $\overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}}$ of all those elements that do not satisfy any one of these properties is given by

$\overline{A_{1}} \bigcup \overline{A_{2}} \bigcup \ldots \bigcup \overline{A_{n}} = |X| - \sum_{i=1}^{n}|A_{n}|+ \sum_{1 \leq i .

Proof:

The proof will show  that every object in the set X is counted the same number of times on both the sides. Suppose $x \in X$ and assume that x is an element of the set on the left hand side of above equation. Then, x has none of the properties $P_{i}$. We need to show that in this case, x is counted only once on the right hand side. This is obvious since x is not in any of the $A_{i}$ and $x \in X$. Thus, X is counted only once in the first summand and is not counted in any other summand since $x \notin A_{i}$ for all i. Now let x have k properties say $P_{i_{1}}$, $P_{i_{2}}$, $\ldots$, $P_{i_{k}}$ (and no  others). Then x is counted once in X. In the next sum, x occurs ${k \choose 2}$ times and so on. Thus, on the right hand side, x is counted precisely,

${k \choose 0}-{k \choose 1}+{k \choose 2}+ \ldots + (-1)^{k}{k \choose k}$

times. Using the binomial theorem, this sum is $(1-1)^{k}$ which is 0 and hence, x is not counted on the right hand side. This completes the proof. QED.

More later,

Nalin Pithwa

### Solution to another S L Loney problem for IITJEE Advanced Mathematics

Exercise XXVII. Problem #32. The sides of a triangle are in AP and the greatest and least angles are $\theta$ and $\phi$. Prove that

$4(1-\cos{\theta})(1-\cos{\phi})=\cos{\theta}+\cos{\phi}$

Proof:

Let a, b, c be in AP. Hence, $a, which in turn implies c is greatest and a is the least.

Hence, $\theta=\angle{C}$ and $\angle{A}$.

Want:

$4(1-\cos{A})(1-\cos{C})=\cos{A}+\cos{C}$

Given:

$b-a=c-b$

$(b-a)^{2}=(b-c)^{2}$. Hence,

$b^{2}-2ab+a^{2}=b^{2}+c^{2}-2bc$

$b^{2}+a^{2}-c^{2}=b^{2}-2bc+2ab$

$2b=a+c$

$4b^{2}=a^{2}+c^{2}+2ac$

$a^{2}+c^{2}-b^{2}=3b^{2}-2ac$

$a^{2}+b^{2}-c^{2}=b^{2}-2bc+2ab$

$b^{2}+c^{2}-a^{2}=b^{2}-2ab+2bc$

Now, we have $1-\cos{A}=1-\frac{b^{2}+c^{2}-a^{2}}{2bc}$ and this is equal to the following:

$\frac{2bc-(b^{2}+c^{2}-a^{2})}{2bc}=\frac{2bc-(b^{2}-2ab+2bc)}{2bc}$

$= \frac{2bc-b^{2}+2ab-2bc}{2bc}=\frac{2ab-b^{2}}{2bc}$.

Also, similarly, we have the following:

$1-\cos{C}=1-\frac{a^{2}+b^{2}-c^{2}}{2ab}=1-\frac{b^{2}-2bc+2ab}{2ab}=\frac{2bc-b^{2}}{2ab}$

$\cos{A}+\cos{C}=\frac{b^{2}+c^{2}-a^{2}}{}+\frac{a^{2}+b^{2}-c^{2}}{2ab}$

$= \frac{b^{2}-2ab+2bc}{2bc}+\frac{b^{2}-2bc+2ab}{2ab}$

$=\frac{a(b^{2}-2ab+2bc)+c(b^{2}-2bc+2ab)}{2abc}$

$=\frac{ab^{2}-2a^{2}b+2abc+b^{2}c-2bc^{2}+2abc}{2abc}$

$=\frac{ab^{2}+b^{2}c-2a^{2}b-2c^{2}b+4abc}{2abc}$

$= \frac{ab+bc-2a^{2}-2c^{2}+4ac}{2ac}$

$=\frac{b(a+c)-2(a-c)^{2}}{2ac}$

$=\frac{2b^{2}-2(a-c)^{2}}{2ac}$

$=\frac{b^{2}-(a-c)^{2}}{2ac}$

$\frac{(b+a-c)}{(b-a+c)}{ac}$

but it is given that $b-a=c-b$, hence, $a+c=2b$, $a+c-b=b$. So the above expression changes to

$= \frac{(b+a-c)(c-b+c)}{ac}$

$= \frac{(2c-b)(a+b-c)}{ac}$

$= \frac{(2c-b)(a+b-\overline{2b-a})}{ac}$

$= \frac{(2c-b)(a-b+c)}{ac}$

$= \frac{(2c-b)(2a-b)}{ac}$

$= \frac{4ac-2bc-2ab+b^{2}}{ac}$

$= 4(1-\cos{A})(1-\cos{C})$.

QED.

### A solution to a S L Loney Part I trig problem for IITJEE Advanced Math

Exercise XXVII. Problem 30.

If a, b, c are in AP, prove that $\cos{A}\cot{A/2}$, $\cos{B}\cot{B/2}$, $\cos{C}\cot{C/2}$ are in AP.

Proof:

Given that $b-a=c-b$

TPT: $\cos{B}\cot{B/2}-\cos{A}\cot{A/2}=\cot{C/2}\cos{C}-\cos{B}\cot{B/2}$. —— Equation 1

Let us try to utilize the following formulae:

$\cos{2\theta}=2\cos^{2}{\theta}-1$ which implies the following:

$\cos{B}=2\cos^{2}(B/2)-1$ and $\cos{A}=2\cos^{2}(A/2)-1$

Our strategy will be reduce LHS and RHS of Equation I to a common expression/value.

$LHS=(\frac{2s(s-b)}{ac}-1)(\frac{\sqrt{\frac{(s)(s-b)}{ac}}}{\sqrt{\frac{(s-a)(s-c)}{ac}}})-\cos{A}\cot{(A/2)}$

which is equal to

$(\frac{2s(s-b)}{ac}-1))(\frac{\sqrt{\frac{(s)(s-b)}{ac}}}{\sqrt{\frac{(s-a)(s-c)}{ac}}})-(2\cos^{2}(A/2)-1)\frac{\cos{A/2}}{\sin{A/2}}$

which is equal to

$(\frac{2s(s-b)}{ac}-1))(\frac{\sqrt{\frac{(s)(s-b)}{ac}}}{\sqrt{\frac{(s-a)(s-c)}{ac}}})-(\frac{2s(s-a)}{bc}-1)\frac{\sqrt{\frac{s(s-a)}{bc}}}{\sqrt{\frac{(s-b)(s-c)}{bc}}}$

which is equal to

$(\frac{2s(s-b)}{ac}-1))\sqrt{s(s-b)}{(s-a)(s-c)}-(\frac{2s(s-a)}{bc}-1)\sqrt{\frac{s(s-a)}{(s-b)(s-c)}}$

which in turn equals

$\sqrt{\frac{s}{(s-a)(s-b)(s-c)}}((\frac{2s(s-b)}{ac}-1)(s-b)-(\frac{2s(s-a)}{bc}-1)(s-a))$

From the above, consider only the expression, given below. We will see what it simplifies to:

$\frac{2s(s-b)^{2}}{ac}-(s-b)-\frac{2s(s-a)^{2}}{bc}+(s-a)$

$=\frac{2s(s-b)^{2}}{ac}-\frac{2s(s-a)^{2}}{bc}+b-a$

$=(\frac{2s}{c})(\frac{(s-b)^{2}}{a}-\frac{(s-a)^{2}}{b})+b-a$

$=\frac{2s(s-b)^{2}}{ca}-\frac{2s(s-a)^{2}}{bc}+c-b$ —- Equation II.

Now, consider RHS of Equation I. Let us see if it also boils down to the above expression after simplification.

$RHS=\cot{(C/2)}\cos{C}-\cos{B}\cot{(B/2)}$

$=(2\cos^{2}{(C/2)}-1)\cot{(C/2)}-(2\cos^{2}({B/2})-1)\cot{(B/2)}$

$=(\frac{2s(s-c)}{ab}-1)\frac{\sqrt{\frac{s(s-c)}{ab}}}{\sqrt{\frac{(s-b)(s-a)}{ab}}}-(\frac{2s(s-b)}{ac})\frac{\sqrt{\frac{s(s-b)}{ac}}}{\sqrt{\frac{(s-a)(s-c)}{ac}}}$

$= \sqrt{\frac{s}{(s-a)(s-b)(s-c)}}((\frac{2s(s-c)}{ab}-1)(s-c)-(\frac{2s(s-b)}{ac}-1)(s-b))$

From equation II and above, what we want is given below:

$\frac{2s(s-c)^{2}}{ab}-(s-c)-\frac{2s(s-b)^{2}}{ac}+(s-b)=\frac{2s(s-b)^{2}}{ac}-\frac{2s(s-a)^{2}}{bc}+c-b$

that is, want to prove that $c(s-c)^{2}+a(s-a)^{2}=2b(s-b)^{2}$

but, it is given that $a+c=2b$ and hence, $c=2b-a$, which means $a+c-b=b$ and $b-a=c-b$

that is, want to prove that

$c(a+b-c)^{2}+a(b+c-a)^{2}=2b(a+c-b)^{2}=2b^{3}$

i.e., want: $c(a+b-c)^{2}+a(b+c-a)^{2}=2b^{3}$

i.e., want: $(2b-a)(a+b-2b+a)^{2}+a(b-a+2b-a)^{2}=2b^{3}$

i.e., want: $(2b-a)(2a-b)^{2}+a(3b-2a)^{2}=2b^{3}$

Now, in the above, $LHS=(2b-a)(4a^{2}+b^{2}-4ab)+a(9b^{2}+4a^{2}-12ab)$

$= 8a^{2}b+2b^{3}-8ab^{2}-4a^{3}-ab^{2}+4ab^{2}+9ab^{2}+4a^{3}-12a^{2}b$

$= 2b^{3}$.

Hence, $LHS+RHS$.

QED.

### Are complex numbers complex ?

You  might perhaps think that complex numbers are complex to handle. Quite contrary. They are easily applied to various kinds of engineering problems and are easily handled in pure math concepts compared to real numbers. Which brings me to another point. Mathematicians are perhaps short of rich vocabulary so they name some object as a “ring”, which is not a wedding or engagement ring at all; there is a “field”, which is not a field of maize at all; then there is a “group”, which is just an abstract object and certainly not a group of people!!

Problem:

Prove the identity:

$({n \choose 0}-{n \choose 2}+{n \choose 4}- \ldots)^{2}+({n \choose 1}-{n \choose 3}+{n \choose 5}-\ldots)^{2}=2^{n}$

Solution:

Denote

$x_{n}={n \choose 0}-{n \choose 2}+{n \choose 4}- \ldots$ and

$y_{n}={n \choose 1}-{n \choose 3}+{n \choose 5}-\ldots$

and observe that $(1+i)^{n}=x_{n}+i y_{n}$

Passing to the absolute value it follows that

$|x_{n}+y_{n}i|=|(1+i)^{n}|=|1+i|^{n}=2^{n/2}$.

This is equivalent to $x_{n}^{2}+y_{n}^{2}=2^{n}$.

More later,

Nalin Pithwa

### Announcement: A Full Scholarship Program

We are Mathematics Hothouse, Bangalore, http://www.mathothouse.com We are pleased to announce that henceforth, every academic year, we will be admitting 5 students with full scholarship or 100% discount, from any part of India, who are talented, deserving or needy, to our program for RMO and INMO coaching. The coaching will be via on-line, live, video interactive Skype sessions mimicking traditional classroom or just classroom coaching or even correspondence course.

If you wish to apply, please write to mathhothouse01@gmail.com

Regards,

Nalin Pithwa

### Some properties of continuous functions : continued

We now turn to the question whether $f(x_{n})$ approximates $f(x)$ when $x_{n}$ approximates x. This is the same as asking: suppose $(x_{n})_{n=1}^{\infty}$ is a sequence of real numbers converging to x, does $(f(x_{n}))_{n=1}^{\infty}$ converges to $f(x)$?

Theorem.

If $f: \Re \rightarrow \Re$ is continuous at $x \in \Re$ if and only if $(f(x_{n}))_{n=1}^{\infty}$ converges to $f(x)$ whenever $(x_{n})_{n=1}^{\infty}$ converges to x, that is,

$\lim_{n \rightarrow \infty}f(x_{n})=f(\lim_{n \rightarrow \infty} x_{n})$.

Proof.

Suppose f is continuous at x and $(x_{n})_{n=1}^{\infty}$ converges to x. By continuity, for every $\varepsilon > 0$, there exists $\delta >0$ such that $|f(x)-f(y)|<\varepsilon$ whenever $|x-y|<\delta$. Since $(x_{n})_{n=1}^{\infty}$ converges to x, for this $\delta >0$, we can find an $n_{0}$ such that $|x-x_{0}|<\delta$ for $n > n_{0}$.

So $|f(x)-f(x_{n})|<\varepsilon$ for $n > n_{0}$ as $|x_{n}-x|<\delta$.

Conversely, suppose $(f(x_{n}))_{n=1}^{\infty}$ converges to $f(x)$ when $(x_{n})_{n=1}^{\infty}$ converges to x. We have to show that f is continuous at x. Suppose f is not continuous at x. That is to say, there is an $\varepsilon >0$ such that however small $\delta$ we may choose, there will be a y satisfying $|x-y|<\delta$ yet $|f(x)-f(y)|\geq \varepsilon$. So for every n, let $x_{n}$ be such a number for which $|x-x_{n}|<(1/n)$ and $|f(x)-f(x_{n})| \geq \varepsilon$. Now, we see that the sequence $(x_{n})_{n=1}^{\infty}$ converges to x. But $(f(x_{n}))_{n=1}^{\infty}$ does not converge to f(x) violating our hypothesis. So f must be continuous at x. QED.

More later,

Nalin Pithwa

### Quick Review of Trigonometric Optimization Methods

Let us review together the four general methods we can use for triangular optimization.

I) Trigonometric Method:

The essence of this method is the observation that the cosine of an angle is at most one and that it equals 1 only when the angle is zero. This fact is applied to the difference between two of the angles A, B and C, holding the third angle fixed, to show that unless those two angles are equal, the objective functionn can be increased (or decreased as the case may be). Consequently, at an optimal solution, these two angles must be equal. If the objective function is symmetric (as is the case, in almost all problems of triangular optimization), then every two of A, B and C must be equal to each other and hence, the triangle ABC must be equilateral.

This method is elementary and easy to apply. Even when the objective function is only partially symmetric, that is, symmetric in two but not in all the three variables, it can be applied to those two variables, holding the third variable fixed. Suppose, for example, that we want to maximize $f(A,B,C)=\cos{A}+2\cos{B}+\cos{C}$. This is symmetric in A and C. So, by the same reasoning as for maximizing $\cos{A}+\cos{B}+\cos{C}$, which at an optimal solution we must have $A=C$. Then, $B=\pi-2A$, which makes f effectively a function of just one variable, viz., $\cos{A}+2\cos(\pi-2A)+\cos{A}$, which equals $2\cos{A}-4\cos^{2}{A}+2$. This can be maximized as a quadratic in $\cos{A}$ either by completing the square or using calculus. The maximum occurs when $A=\cos^{-1}{1/4}$. Thus, the maximum value of $\cos{A}+2\cos{B}+\cos{C}$ for a triangle ABC is $1/4$. The method, of course, fails if the function is not even partially symmetric. This is not surprising. Basically, in a triangular optimization problem, we are dealing with a function $f(A,B,C)$ of three variables. Because of the constraint $A+B+C=\pi$, any one of the variables can be expressed in terms of the other two. This effectively makes f a function of two variables. Optimization of functions of several variables requires advanced methods. It is only when f satisfies some other conditions such as partial symmetry that we can hope to reduce the number of variables further so that elementary methods can be applied.

II) Algebraic Method:

The essence of this method is to reduce the optimization problem to some inequality using suitable trigonometric formulae or identities. The inequality is then established using some standard inequality such as the AM-GM-HM inequality, or Jensen’s inequality, or sometimes, by doing some more basic work. The fundamental ideas are very simple, viz., (a) the square of any real number is non-negative and is zero only when that number is zero, and (b) the sum of two or more non-negative numbers is non-negative and vanishes if and only if each of the term is zero. When this method works, it works elegantly. But it is not always easy to come up with the right algebraic manipulations. Sometimes, certain simplifying substitutions have to be used. Still, it is an elementary method and deserves to be tried.

III) Jensen’s inequality:

This is a relatively advanced method. It is directly applicable when the objective function is, or can be recast, in a certain form, viz., $h(A)+h(B)+h(C)$, where h is a function of one variable whose second derivative maintains the same sign over a suitable interval. But, even when h fails to do so, the method can sometimes be applied with a suitable conversion of the problem.

IV) Lagrange’s Multipliers:

This is a highly advanced method based on the calculus of functions of several variables. It is applicable to all types of objective functions, not just those that are symmetric or partially symmetric. When applied to triangular optimization problems with symmetric objective functions, the optimal solution is either degenerate or an equilateral triangle.

Naturally, for a particular given problem, some of these methods may work better than others. The method of Lagrange’s multipliers is the surest but the most mechanical of all the four. The algebraic method is artistic and sometimes gives the answer very fast. Jensen’s inequality also works fast once you are able to cast the objective function in a certain form. Such a recasting may involve some ingenuity sometimes. The trouble is that both these methods work only in the case of an  optimization problem where the objective function is symmetric. And, in such cases, the method of Lagrange’s multipliers makes a mincemeat of the problem. From an examination point of view, this is a boon if a question about triangular optimization is asked in a “fill in the blanks” or “multiple choice” form, where you don’t have to show any reasoning. if the objective function is symmetric, then the optimal solution is either degenerate or an equilateral triangle. But, degenerate triangles are often excluded from the very definition of a triangle because of the requirement that the three vertices of a triangle must be distinct and non-collinear and, in any case, such absurdities are unlikely to be asked in an examination! So, it is a safe bet to simply assume that the optimal solution is an equilateral triangle and proceed with further work (namely, calculating the value of the objective function for an equilateral triangle). This saves you a lot of time.

More later,

Nalin Pithwa

### The Sieve — elementary combinatorial applications

One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Erathosthenes). This relates the cardinality of the union of certain sets to  the cardinalities of the intersections of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps, it contains terms alternating in sign, and in general it has too many of them!

A natural setting for the sieve is in the language of probability theory. Of course, this only means a division by the cardinality of the underlying set, but it has the advantage that independence of occurring events can be defined. Situations in which events are almost independent are extremely important in number theory and also arise in certain combinatorial applications. Number theorists have developed ingenious methods to estimate the formula when the events (usually divisibility by certain primes) are almost independent. We give here the combinatorial background of some of these methods. Their actual use, however, rests upon complicated number theoretic considerations which are here illustrated only by two problems.

It should be emphasized that the sieve formula has many applications in quite different situations.

A beautiful general theory of inclusion-exclusion, usually referred to as the theory of the Mobius function is due to L. Weisner, P. Hall and G. C. Rota.

Question 1: In a high school class of 30 pupils, 12 pupils like mathematics, 14 like physics and 18 chemistry, 5 pupils like both mathematics and physics, 7 both physics and chemistry, 4 pupils like mathematics and chemistry. There are 3 who like all three subjects. How many pupils do not like any of them?

Question 2: (a) The Sieve Formula:

Let $A_{1}, \ldots, A_{n}$ be arbitrary events of a probability space $(\Omega, P)$. For each

$I \subseteq \{ 1, \ldots , n\}$, let

$A_{I}= \prod_{i\in I}A_{i}$, $A_{\phi}=\Omega$

and let $\sigma_{k}=\sum_{|I|=k}P(A_{I})$, $\sigma_{0}=1$

Then, $P(A_{1}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sigma_{j}$

Question 2: (b) (Inclusion-Exclusion Formula)

Let $A_{1}, \ldots, A_{n} \subseteq S$, where S is a finite set, and let

$A_{I}=\bigcap_{ j \in J}A_{j}$, $A_{\phi}=S$. Then,

$|S-(A_{1}\cup \ldots \cup A_{n})|=\sum_{J \subset \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Hints:

1) The number of pupils who like mathematics or physics is not $12+14$. By how much is 26 too  large?

2) Determine the contribution of any atom of the Boolean Algebra generated by $A_{1},, \ldots A_{n}$ on each side.

Solutions.

1) Let us subtract from 30 the number of pupils who like mathematics, physics, chemistry, respectively:

$30-12-14-13$.

This way, however, a student who likes both mathematics and physics is subtracted twice; so we have to add them back, and also for the other pairs of subjects:

$30-12-14-13+5+7+4$.

There is still trouble with those who like all three subjects. They were subtracted 3 times, but back 3 times, so we have to subtract them once more to get the result:

$30-12-14-13+5+7+4-3=4$/

2) (a) Let $B=A_{1}A_{2}\ldots A_{k}\overline A_{k+1}\ldots \overline A_{n}$

be any atom of the Boolean algebra generated by $A_{1}, A_{2}, \ldots A_{n}$ (with an appropriate choice of indices, every atom has such a form.) Every event in the formula is the union of certain (disjoint) atoms; let us express each $P(A_{I})$ and $P(A_{1}+A_{2}+\ldots +A_{n})$ as the sum of the probabilities of the corresponding atoms. We show that the probability of any given atom cancels out.

The coefficient of $P(B)$ on the left hand side is

$1, if k \neq 0$ and $0, if k=0$

B occurs in $A_{I}$ if $I \subseteq \{ 1, \ldots k\}$. so its coefficient on the right hand side is

$\sum_{j=1}^{k}\left( \begin{array}{c} k \\ j \end{array} \right) (-1)^{j}=1-(1-1)^{k}=1, k \neq 04, and$latex 0 if k =0\$.

Thus, $P(B)$ has the same coefficient on both sides, which proves part a.

Solution (b):

Choose an element x of S by a uniform distribution. Then, $A_{i}$ can be identified with the event that

$x \in A_{I}$, and we have

$P(A_{i})=\frac{|A_{i}|}{|S|}$

So, we have, by the above,

$P(A_{1}+A_{2}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sum_{|I|=j}\frac{|A_{I}|}{|S|}$, where

$\sum_{\phi \neq I \subseteq \{ 1, \ldots n\} }(-1)^{|I|-1}\frac{A_{I}}{|S|}$, or equivalently

$P(\overline{A_{1}}\ldots \overline{A_{n}})=1-P(A_{1}+\ldots + A_{n})$, which in turn equals,

$1- \sum_{\phi \neq I \subseteq \{ 1, \ldots , n\}}(-1)^{|I|-1}\frac{|A|}{|S|}$

The assertion (b) follows on multiplying by $|S|$.

More later,

Nalin Pithwa