IITJEE Advanced Mathematics « Mathematics Hothouse

Category Archives: IITJEE Advanced Mathematics

Solutions to Birthday Problems: IITJEE Advanced Mathematics

May 23, 2017 – 9:04 pm

In the following problems, each year is assumed to be consisting of 365 days (no leap year):

Problem 1:

What is the least number of people in a room such that it is more likely than not that at least two people will share the same birthday?

Solution 1:

The probability of the second person having a different birthday from the first person is $\frac{364}{365}$ . The probability of the first three persons having different birthdays is $\frac{364}{365} \times \frac{363}{365}$ . In this way, the probability of all n persons in a room having different birthdays is $P(n) = \frac{364}{365} \times \frac{363}{365} \times \frac{362}{365} \times \ldots \frac{365-n+1}{365}$ . For the value of n, when P(n) falls just below 1/2 is the least number of people in a room when the probability of at least two people having the same birthday becomes greater than one half (that is, more likely than not). Now, one can make the following table:

$\begin{tabular}{|c|c|}\hline N & P(n) \\ \hline 2 & 364/365 \\ \hline 3 & 0.9918 \\ \hline 4 & 0.9836 \\ \hline 5 & 0.9729 \\ \hline 6 & 0.9595 \\ \hline 7 & 0.9438 \\ \hline 8 & 0.9257 \\ \hline 9 & 0.9054 \\ \hline 10 & 0.8830 \\ \hline 11 & 0.8589 \\ \hline 12 & 0.8330 \\ \hline 13 & 0.8056 \\ \hline 14 & 0.7769 \\ \hline 15 & 0.7471 \\ \hline 16 & 0.7164 \\ \hline 17 & 0.6850 \\ \hline 18 &0.6531 \\ \hline 19 & 0.6209 \\ \hline 20 & 0.5886 \\ \hline 21 & 0.5563 \\ \hline 22 & 0.5258 \\ \hline 23 & 0.4956 \\ \hline \end{tabular}$

Thus, the answer is 23. One may say that during a football match with one referee, it is more likely than not that at least two people on the field have the same birthday! 🙂 🙂 🙂

Problem 2:

You are in a conference. What is the least number of people in the conference (besides you) such that it is more likely than not that there is at least another person having the same birthday as yours?

Solution 2:

The probability of the first person having a different birthday from yours is $\frac{364}{365}$ . Similarly, the probability of the first two persons not having the same birthday as yours is $\frac{(364)^{2}}{(365)^{2}}$ . Thus, the probability of n persons not having the same birthday as yours is $\frac{(364)^{n}}{(365)^{n}}$ . When this value falls below 0.5, then it becomes more likely than not that at least another person has the same birthday as yours. So, the least value of n is obtained from $(\frac{364}{365})^{n}<\frac{1}{2}$ . Taking log of both sides, we solve to get $n>252.65$ . So, the least number of people required is 253.

Problem 3:

A theatre owner announces that the first person in the queue having the same birthday as the one who has already purchased a ticket will be given a free entry. Where (which position in the queue) should one stand to maximize the chance of earning a free entry?

Solution 3:

For the nth person to earn a free entry, first $(n-1)$ persons must have different birthdays and the nth person must have the same birthday as that of one of these previous $(n-1)$ persons. The probability of such an event can we written as

$P(n) = [\frac{364}{365} \times \frac{363}{365} \times \frac{362}{365} \times \ldots \frac{365-n+2}{365}] \times \frac{n-1}{365}$

For a maximum, we need $P(n) > P(n+1)$ . Alternatively, $\frac{P(n)}{P(n+1)} >1$ . Using this expression for P(n), we get $\frac{365}{365-n} \times \frac{n-1}{n} >1$ . Or, $n^{2}-n-365>0$ . For positive n, this inequality is satisfied first for some n between 19 and 20. So, the best place in the queue to get a free entry is the 20th position.

More later,

Nalin Pithwa.

Birthday Probability Problems: IITJEE Advanced Mathematics

May 23, 2017 – 1:35 am

In the following problems, each year is assumed to be consisting of 365 days (no leap year):

What is the least number of people in a room such that it is more likely than not that at least two people will share the same birthday?
You are in a conference. What is the least number of people in the conference (besides you) such that it is more likely than not that there is at least another person having the same birthday as yours?
A theatre owner announces that the first person in the queue having the same birthday as the one who has already purchased a ticket will be given a free entry. Where (which position in the queue) should one stand to maximize the chance of earning a free entry?

I will put up the solutions on this blog tomorrow. First, you need to make a whole-hearted attempt.

Nalin Pithwa.

By nkpithwa | Also posted in applications of maths, probability theory | Comments (0)

Limits that arise frequently

February 23, 2017 – 7:18 pm

We continue our presentation of basic stuff from Calculus and Analytic Geometry, G B Thomas and Finney, Ninth Edition. My express purpose in presenting these few proofs is to emphasize that Calculus, is not just a recipe of calculation techniques. Or, even, a bit further, math is not just about calculation. I have a feeling that such thinking nurtured/developed at a young age, (while preparing for IITJEE Math, for example) makes one razor sharp.

We verify a few famous limits.

Formula 1:

If $|x|<1$ , $\lim_{n \rightarrow \infty}x^{n}=0$

We need to show that to each $\in >0$ there corresponds an integer N so large that $|x^{n}|<\in$ for all n greater than N. Since $\in^{1/n}\rightarrow 1$ , while $|x|<1$ . there exists an integer N for which $\in^{1/n}>|x|$ . In other words,

$|x^{N}|=|x|^{N}<\in$ . Call this (I).

This is the integer we seek because, if $|x|<1$ , then

$|x^{n}|<|x^{N}|$ for all $n>N$ . Call this (II).

Combining I and II produces $|x^{n}|<\in$ for all $n>N$ , concluding the proof.

Formula II:

For any number x, $\lim_{n \rightarrow \infty}(1+\frac{x}{n})^{n}=e^{x}$ .

Let $a_{n}=(1+\frac{x}{n})^{n}$ . Then, $\ln {a_{n}}=\ln{(1+\frac{x}{n})^{n}}=n\ln{(1+\frac{x}{n})}\rightarrow x$ ,

as we can see by the following application of l’Hopital’s rule, in which we differentiate with respect to n:

$\lim_{n \rightarrow \infty}n\ln{(1+\frac{x}{n})}=\lim_{n \rightarrow \infty}\frac{\ln{(1+x/n)}}{1/n}$ , which in turn equals

$\lim_{n \rightarrow \infty}\frac{(\frac{1}{1+x/n}).(-\frac{x}{n^{2}})}{-1/n^{2}}=\lim_{n \rightarrow \infty}\frac{x}{1+x/n}=x$ .

Now, let us apply the following theorem with $f(x)=e^{x}$ to the above:

(a theorem for calculating limits of sequences) the continuous function theorem for sequences:

Let $a_{n}$ be a sequence of real numbers. If $\{a_{n}\}$ be a sequence of real numbers. If $a_{n} \rightarrow L$ and if f is a function that is continu0us at L and defined at all $a_{n}$ , then $f(a_{n}) \rightarrow f(L)$ .

So, in this particular proof, we get the following:

$(1+\frac{x}{n})^{n}=a_{n}=e^{\ln{a_{n}}}\rightarrow e^{x}$ .

Formula 3:

For any number x, $\lim_{n \rightarrow \infty}\frac{x^{n}}{n!}=0$

Since $-\frac{|x|^{n}}{n!} \leq \frac{x^{n}}{n!} \leq \frac{|x|^{n}}{n!}$ ,

all we need to show is that $\frac{|x|^{n}}{n!} \rightarrow 0$ . We can then apply the Sandwich Theorem for Sequences (Let $\{a_{n}\}$ , $\{b_{n}\}$ and $\{c_{n}\}$ be sequences of real numbers. if $a_{n}\leq b_{n}\leq c_{n}$ holds for all n beyond some index N, and if $\lim_{n\rightarrow \infty}a_{n}=\lim_{n\rightarrow \infty}c_{n}=L$ ,, then $\lim_{n\rightarrow \infty}b_{n}=L$ also) to conclude that $\frac{x^{n}}{n!} \rightarrow 0$ .

The first step in showing that $|x|^{n}/n! \rightarrow 0$ is to choose an integer $M>|x|$ , so that $(|x|/M)<1$ . Now, let us the rule (formula 1, mentioned above), so we conclude that: $(|x|/M)^{n}\rightarrow 0$ . We then restrict our attention to values of $n>M$ . For these values of n, we can write:

$\frac{|x|^{n}}{n!}=\frac{|x|^{n}}{1.2 \ldots M.(M+1)(M+2)\ldots n}$ , where there are $(n-M)$ factors in the expression $(M+1)(M+2)\ldots n$ , and

the RHS in the above expression is $\leq \frac{|x|^{n}}{M!M^{n-M}}=\frac{|x|^{n}M^{M}}{M!M^{n}}=\frac{M^{M}}{M!}(\frac{|x|}{M})^{n}$ . Thus,

$0\leq \frac{|x|^{n}}{n!}\leq \frac{M^{M}}{M!}(\frac{|x|}{M})^{n}$ . Now, the constant $\frac{M^{M}}{M!}$ does not change as n increases. Thus, the Sandwich theorem tells us that $\frac{|x|^{n}}{n!} \rightarrow 0$ because $(\frac{|x|}{M})^{n}\rightarrow 0$ .

That’s all, folks !!

Aufwiedersehen,

Nalin Pithwa.

By nkpithwa | Also posted in calculus, Cnennai Math Institute Entrance Exam, pure mathematics | Tagged advanced calculus | Comments (0)

Cauchy’s Mean Value Theorem and the Stronger Form of l’Hopital’s Rule

February 12, 2017 – 5:26 am

Reference: Thomas, Finney, 9th edition, Calculus and Analytic Geometry.

Continuing our previous discussion of “theoretical” calculus or “rigorous” calculus, I am reproducing below the proof of the finite limit case of the stronger form of l’Hopital’s Rule :

L’Hopital’s Rule (Stronger Form):

Suppose that

$f(x_{0})=g(x_{0})=0$

and that the functions f and g are both differentiable on an open interval $(a,b)$ that contains the point $x_{0}$ . Suppose also that $g^{'} \neq 0$ at every point in $(a,b)$ except possibly at $x_{0}$ . Then,

$\lim_{x \rightarrow x_{0}}\frac{f(x)}{g(x)}=\lim_{x \rightarrow x_{0}}\frac{f^{x}}{g^{x}}$ ….call this equation I,

provided the limit on the right exists.

The proof of the stronger form of l’Hopital’s Rule is based on Cauchy’s Mean Value Theorem, a mean value theorem that involves two functions instead of one. We prove Cauchy’s theorem first and then show how it leads to l’Hopital’s Rule.

Cauchy’s Mean Value Theorem:

Suppose that the functions f and g are continuous on $[a,b]$ and differentiable throughout $(a,b)$ and suppose also that $g^{'} \neq 0$ throughout $(a,b)$ . Then there exists a number c in $(a,b)$ at which

$\frac{f^{'}(c)}{g^{'}(c)} = \frac{f(b)-f(a)}{g(b)-g(a)}$ …call this II.

The ordinary Mean Value Theorem is the case where $g(x)=x$ .

Proof of Cauchy’s Mean Value Theorem:

We apply the Mean Value Theorem twice. First we use it to show that $g(a) \neq g(b)$ . For if $g(b)$ did equal to $g(a)$ , then the Mean Value Theorem would give:

$g^{'}(c)=\frac{g(b)-g(a)}{b-a}=0$ for some c between a and b. This cannot happen because $g^{'}(x) \neq 0$ in $(a,b)$ .

We next apply the Mean Value Theorem to the function:

$F(x) = f(x)-f(a)-\frac{f(b)-f(a)}{g(b)-g(a)}[g(x)-g(a)]$ .

This function is continuous and differentiable where f and g are, and $F(b) = F(a)=0$ . Therefore, there is a number c between a and b for which $F^{'}(c)=0$ . In terms of f and g, this says:

$F^{'}(c) = f^{'}(c)-\frac{f(b)-f(a)}{g(b)-g(a)}[g^{'}(c)]=0$ , or

$\frac{f^{'}(c)}{g^{'}(c)}=\frac{f(b)-f(a)}{g(b)-g(a)}$ , which is II above. QED.

Proof of the Stronger Form of l’Hopital’s Rule:

We first prove I for the case $x \rightarrow x_{o}^{+}$ . The method needs no change to apply to $x \rightarrow x_{0}^{-}$ , and the combination of those two cases establishes the result.

Suppose that x lies to the right of $x_{o}$ . Then, $g^{'}(x) \neq 0$ and we can apply the Cauchy’s Mean Value Theorem to the closed interval from $x_{0}$ to x. This produces a number c between $x_{0}$ and x such that $\frac{f^{'}(c)}{g^{'}(c)}=\frac{f(x)-f(x_{0})}{g(x)-g(x_{0})}$ .

But, $f(x_{0})=g(x_{0})=0$ so that $\frac{f^{'}(c)}{g^{'}(c)}=\frac{f(x)}{g(x)}$ .

As x approaches $x_{0}$ , c approaches $x_{0}$ because it lies between x and $x_{0}$ . Therefore, $\lim_{x \rightarrow x_{0}^{+}}\frac{f(x)}{g(x)}=\lim_{x \rightarrow x_{0}^{+}}\frac{f^{'}(c)}{g^{'}(c)}=\lim_{x \rightarrow x_{0}^{+}}\frac{f^{'}(x)}{g^{'}(x)}$ .

This establishes l’Hopital’s Rule for the case where x approaches $x_{0}$ from above. The case where x approaches $x_{0}$ from below is proved by applying Cauchy’s Mean Value Theorem to the closed interval $[x,x_{0}]$ , where $x< x_{0}$ . QED.

By nkpithwa | Also posted in calculus, Cnennai Math Institute Entrance Exam, pure mathematics | Comments (0)

The Sandwich Theorem or Squeeze Play Theorem

February 5, 2017 – 10:05 am

It helps to think about the core concepts of Calculus from a young age, if you want to develop your expertise or talents further in math, pure or applied, engineering or mathematical sciences. At a tangible level, it helps you attack more or many questions of the IIT JEE Advanced Mathematics. Let us see if you like the following proof, or can absorb/digest it:

Reference: Calculus and Analytic Geometry by Thomas and Finney, 9th edition.

The Sandwich Theorem:

Suppose that $g(x) \leq f(x) \leq h(x)$ for all x in some open interval containing c, except possibly at $x=c$ itself. Suppose also that $\lim_{x \rightarrow c}g(x)= \lim_{x \rightarrow c}h(x)=L$ . Then, $\lim_{x \rightarrow c}f(x)=c$ .

Proof for Right Hand Limits:

Suppose $\lim_{x \rightarrow c^{+}}g(x)=\lim_{x \rightarrow c^{+}}h(x)=L$ . Then, for any $\in >0$ , there exists a $\delta >0$ such that for all x, the inequality $c<x<c+\delta$ implies $L-\in<g(x)<L+\in$ and $L-\in<h(x)<L+\in$ ….call this (I)

These inequalities combine with the inequality $g(x) \leq f(x) \leq h(x)$ to give

$L-\in <g(x) \leq f(x) \leq h(x)<L+\in$

$L-\in <f(x)<L+\in$

$-\in <f(x)-L<\in$ ….call this (II)

Therefore, for all x, the inequality $c<x<c+\delta$ implies $|f(x)-L|<\in$ . …call this (III)

Proof for LeftHand Limits:

Suppose $\lim_{x \rightarrow c^{-}} g(x)=\lim_{x \rightarrow c^{-}}=L$ . Then, for $\in >0$ there exists a $\delta >0$ such that for all x, the inequality $c-\delta <x<c$ implies $L-\in<g(x)<L+\in$ and $L-\in<h(x)<L+\in$ …call this (IV).

We conclude as before that for all x, $c-\delta <x<c$ implies $|f(x)-L|<\in$ .

Proof for Two sided Limits:

If $\lim_{x \rightarrow c}g(x) = \lim_{x \rightarrow c}h(x)=L$ , then $g(x)$ and $h(x)$ both approach L as $x \rightarrow c^{+}$ and as $x \rightarrow c^{-}$ so $\lim_{x \rightarrow c^{+}}f(x)=L$ and $\lim_{x \rightarrow c^{-}}f(x)=L$ . Hence, $\lim_{x \rightarrow c}f(x)=L$ . QED.

Let me know your feedback on such stuff,

Nalin Pithwa

By nkpithwa | Also posted in Cnennai Math Institute Entrance Exam, pure mathematics | Comments (0)

Maxima and Minima using calculus

May 28, 2016 – 4:41 pm

Problem:

The vertices of an $(n+1)$ -gon lie on the sides of a regular n-gon and divide its perimeter into parts of equal length. How should one construct the $(n+1)-$ gon so that its area is :

(a) maximum

(b) minimum

Hint only:

[One of the golden rule of solving problems in math/physics is to draw diagrams, as had benn emphasized by the maverick American physics Nobel Laureate, Richard Feynman. He expounded this technique even in software development. So, in the present problem, first draw several diagrams.]

There exists a side $B_{1}B_{2}$ of the $(n+1)$ -gon that lies entirely on a side $A_{1}A_{2}$ of the n-gon. Let $b=B_{1}B_{2}$ and $b=A_{1}A_{2}$ . Show that $b=\frac{n}{n+1}a$ . Then, for $x=A_{1}B_{1}$ , we have $0 \leq x \leq \frac{n}{n+1}$ and the area S of the $(n+1)$ -gon is given by

$S(x)=\frac{\sin{\phi}}{2}\Sigma_{i=1}^{n}(\frac{i-1}{n+1}a+x)(\frac{n-i+1}{n+1}a-x)$

where $\phi=\angle{A_{1}A_{2}A_{3}}$ . Thus, $S(x)$ is a quadratic function of x. Show that $S(x)$ is a minimal when $x=0$ or $x=\frac{a}{n+1}$ and $S(x)$ is maximal when $x=\frac{a}{2(n+1)}$ .

Let me know if you have any trouble when you attempt it,

-Nalin Pithwa

By nkpithwa | Also posted in calculus, Cnennai Math Institute Entrance Exam, ISI Kolkatta Entrance Exam | Tagged optimization | Comments (0)

Triangle inequality and max-min

May 19, 2016 – 7:35 am

Here is a problem I culled from Prof. Titu Andreescu’s literature (Geometric maxima and minima) for IITJEE Mathematics:

Problem:

Find the greatest real number k such that for any triple of positive numbers a, b, c such that $kabc > a^{3}+b^{3}+c^{3}$ , there exists a triangle with side lengths a, b, c.

Solution:

We have to find the greatest real number k such that for any a, b, $c > 0$ with $a + b \leq c$ , we have $kabc \leq a^{3}+b^{3}+c^{3}$ . First take $b=a$ and $c=2a$ . Then, $2ka^{3} \leq 10a^{3}$ , that is, $k \leq 5$ . Conversely, let $k=5$ . Set $c=a+b+x$ , where $x \geq 0$ . Then,

$a^{3}+b^{3}+c^{3}-5abc =2(a+b)(a-b)^{2}+(ab+3a^{2}+3b^{2})x+3(a+b)x^{2}+x^{3} \geq 0$ .

QED.

More later,

Nalin Pithwa

By nkpithwa | Also posted in IITJEE Mains | Tagged maxima minima, triangle inequality | Comments (0)

Maxima and minima — using calculus — for IITJEE Advanced Mathematics

May 17, 2016 – 9:29 am

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

By nkpithwa | Also posted in calculus | Comments (0)

A Trigonometry problem for IITJEE Advanced Mathematics or Mathematics Olympiad

April 9, 2016 – 10:22 am

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 Cauchy–Schwarz 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}$

$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

By nkpithwa | Also posted in Trigonometry | Tagged Cauchy Schwarz inequality | Comments (0)

Inclusion Exclusion Principle theorem and examples

February 13, 2016 – 11:27 am

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 <j \leq n}|A_{i} \bigcup A_{j}|- \ldots + \{ (-1)^{k} \sum_{1 \leq i_{1} < i_{2}< \ldots < i_{k} \leq n}|A_{i_{1} \bigcup A_{i_{2}}} \ldots \bigcup A_{i_{k}}|\}+ \ldots+ (-1)^{n}|A_{1} \bigcup A_{2} \ldots \bigcup A_{n}|$ .

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

By nkpithwa | Also posted in Cnennai Math Institute Entrance Exam, combinatorics or permutations and combinations, RMO | Comments (0)

Mathematics Hothouse

Category Archives: IITJEE Advanced Mathematics

Solutions to Birthday Problems: IITJEE Advanced Mathematics

Birthday Probability Problems: IITJEE Advanced Mathematics

Limits that arise frequently

Cauchy’s Mean Value Theorem and the Stronger Form of l’Hopital’s Rule

The Sandwich Theorem or Squeeze Play Theorem

Maxima and Minima using calculus

Triangle inequality and max-min

Maxima and minima — using calculus — for IITJEE Advanced Mathematics

A Trigonometry problem for IITJEE Advanced Mathematics or Mathematics Olympiad

Inclusion Exclusion Principle theorem and examples

Pages

Categories

Archives

Search

Blogroll

RSS Feeds

Meta