Monthly Archives: March 2015

Trigonometric Optimization continued

Prove that in any acute angled triangle ABC, \tan {A}+\tan{B}+\tan{C} \geq 3\sqrt{3} with equality holding if and only if the triangle is equilateral. (IITJEE 1998)

Proof:

Suggestion: Try this without reading further! It looks complicated, but need not be so!! Then, after you have attempted whole-heartedly, compare your solution with the one below.

The solution to the above problem is based on the well-known identity:

\tan{A}+\tan{B}+\tan{C}=\tan{A}\tan{B}\tan{C}. For brevity, denote \tan{A}, \tan{B}, \tan{C}

by x, y and z respectively. As ABC is acute-angled, x, y, z are all positive and the AM-GM inequality which says

x+y+z \geq 3{(xyz)}^{1/3} can be applied. Taking cubes of both the sides and cancelling

x+y+z, (which is positive) this gives (x+y+z)^{2} \geq 27. Taking square root we get the desired inequality. If equality is to hold, then it must also hold in the AM-GM inequality, which can happen if and only if

x=y=z, that is, if and only if the triangle is equilateral.

Still, this approach requires some caution. Actually, there are so many trigonometric identities that there is no unanimity as to which ones among them are standard enough to be assumed without proof !! But, of course, the IITJEE Examinations, both Mains and Advanced are multiple choice only.

More later,

Nalin Pithwa

An example of Trigonometric Optimization

Problem: If A, B, C are angles of a triangle, then find the maximum value of 

\cos{A}+\cos{B}+\cos{C} expressed as a reduced rational. (IITJEE 1984).

First Hint: Prove that the maximum must occur for an equilateral triangle.

Second Hint: For a fixed value of one of the three angles, show that the maximum must occur when the other two are equal.

Solution:

Here, the three angles A, B, C are constrained by the requirement that they are non-negative and add up to

\pi. Let S be the set of all ordered triples of the form (A,B,C) which satisfy these constraints, that is,

S= \{ (A,B,C)= A \geq 0, B \geq 0, C \geq 0 and A+B+C=\pi\}

and denote \cos{A}+\cos{B}+\cos{C} by f(A,B,C). Then, the problem amounts to finding the maximum value of the function f over the set S.

Now, suppose (A,B,C) \in S. We claim that unless A=B, we can find some

(A^{'}, B^{'}, C^{'}) \in S such that f(A^{'},B^{'},C^{'})>f(A,B,C). Indeed, we let C^{'}=C and A^{'}=B^{'}=\frac{A+B}{2}. Note that A^{'}+B^{'}=A+B and hence,

(A^{'},B^{'},C^{'}) \in S. Note that \cos{\frac{A+B}{2}}=\cos{\frac{A^{'}+B^{'}}{2}} \neq 0

(except in the degenerate case where A=B=\pi/2). Further, \cos{\frac{A^{'}-B^{'}}{2}}=\cos{0}=1 which is greater than \cos{\frac{A-B}{2}}. This gives,

f(A,B,C)=\cos{A}+\cos{B}+\cos{C}=2\cos{\frac{A+B}{2}}\cos{\frac{A-B}{2}}+\cos{C}

which is less than

2\cos{\frac{A^{'}+B^{'}}{2}}\cos{\frac{A^{'}-B^{'}}{2}}+\cos{C^{'}}

which equals \cos{A^{'}}+\cos{B^{'}}+\cos{C^{'}}=f(A^{'},B^{'},C^{'}).

By a similar reasoning, unless B=C, we can find some (A^{''}, B^{''}, C^{''}) \in S such that

f(A,B,C)<f(A^{''}, B^{''}, C^{''}). A similar assertion holds if C \neq A. It then follows that when

f(A,B,C) is maximum, A, B, C must be all equal and hence, each equals \pi/3

(since A+B+C=\pi/3). But, f(\pi/3,\pi/3,\pi/3)=1/2+1/2+1/2=3/2. So, the maximum value of

\cos{A}+\cos{B}+\cos{C}=3/2.

More later,

Nalin Pithwa

Some basic results in number theory — part 1

Theorem (1): The product of any n consecutive integers is divisible by n!.

Proof (1): 

For \frac {(m+1)(m+2) \ldots (m+n)}{n!}=\frac{(m+n)!}{m!n!}, and to show that the last expression is an integer it is sufficient to show that any prime p which occurs in m!n! to at least as high as a power in

(m+n)!. Thus, we have to show that

I[\frac{(m+n)}{p}]+I[\frac{(m+n)}{p^{2}}]+I[\frac{(m+n)}{p^{3}}]+\ldots is greater than or equal to

I[m/p]+I[m/p^{2}]+I[m/p^{3}]+\ldots +I[n/p]+I[n/p^{2}]+I[n/p^{3}]+\ldots.

Note: The  Symbol I[x/y]: If  a is a fraction or an irrational number, the symbol I(a) will be used to denote the integral part of a.

Now, I[\frac{(m+n)}{p}] \geq I[m/p]+I[n/p], and the same is true if we replace p by p^{2}, p^{3} in succession, hence the result in question.

Theorem (2): If n is a prime, then {n \choose r} is divisible by n.

For by the preceding n(n-1)(n-2)\ldots (n-r+1) is divisible by r! and since n is a prime and r is supposed to be less than n, r! is prime to n. Hence,

r! is a divisor of (n-1)(n-2)\ldots (n-r+1)

and n(n-1)\ldots (n-r+1)/r! is divisible by n.

Thus, if a is a prime, all the coefficients in the expansion of (1+x)^{n} except the first and last are divisible by n.

Homework:

1) Find the highest power of 5  contained in 158!

2) If n is an odd prime, the integral part of (\sqrt{5}+2)^{n}-2^{n+1} is divisible by 20n.

More later,

Nalin Pithwa

Basic enumeration — continued

(a) How many possibilities are there to distribute k forints (Hungarian currency) among n people so that each receive at least one?

(b) Suppose that we do and insist that each person receives something. What will be the number of distributions in this case?

Hint (a)

Imagine k 1-forint coins in a row and suppose that the people come one by one and pick up forints as long as you allow them.

Hint (b)

Reduce to the previous case by borrowing 1 forint from each person.

Solution (a):

If we distribute the forints by the procedure described in the hint, we have to say “Next please” n-1 times. If we determine at which points (after which coins) we say this we uniquely determine the distribution. There are

k-1 possible points to switch and we have to choose n-1 out of these. Hence, the result is

{{k-1} \choose {n-1}}.

Solution (b):

Borrow one forint from each person. If we distribute the n+k forints, we then have in such a way that each person gets at least one, we should then have done the same as if we had distributed the k forints without this requirement. More precisely, distributions of n+k forints among persons so that each one gets at least one are in one to one correspondence with all distributions of n forints among k persons. Hence, the answer is

{{n+k-1} \choose {n-1}}.

More later,

Nalin Pithwa

Basic combinatorics — basic enumeration

I. Basic Enumeration:

There is no rule which says that enumeration problems, even the simplest ones, must have solutions expressible as closed formulas. Some have, of course, and one important thing to be learnt here is how to recognize such problems. Another approach, avoiding the difficulty of trying to produce a closed formula, is to look for “substitute” solutions in other forms such as formulae involving summations, recurrence relations or generating functions. A typical (but not unique or universal) technique for solving an enumeration problem, in one or more parameters, is to find a recurrence relation, deduce a formula for the generating function (the recurrence relation is usually equivalent to a differential equation involving this function) and finally, where possible, to obtain the coefficients in the Taylor expansion of the generating function.

However, it should be pointed out that, in many cases, elementary transformations of the problems may lead to another problem already solved. For example, it may be possible by such transformations to represent each element to be counted as the result of n consecutive decisions such that there are a_{i} possible choices at the ith step. The answer would then be a_{1}a_{2}a_{3}\ldots a_{n}. This is particularly useful when each decision if independent of all the previous decisions. Finding such a situation equivalent to the given problem is usually difficult and a matter of luck combined with experience.

1) In a shop there are k kinds of postcards. We want to send postcards to n friends. How many different ways can this be done? What happens if we want to send them different cards? What happens if we want to send two different cards to each of them(but different persons may get the same card)?

Hint:

Decide about the persons one by one.

Solution:

I. i.

The first person may be sent any of the k kinds of postcards. No matter which one he is sent, we may still send the second one any of the k kinds, so there are k \times k = k^{2} ways to send cards to the first two friends. Again, whatever they are sent, the third friend can still be sent k kinds, etc. So there are k^{n} ways to send out the cards.

I.ii

If they have to be sent different cards, the first person can still be sent any of the k cards. But for any choice of this card, there are only k-1 kinds of cards left for the second person, whatever the first and second friends receive the third one can get one of k-2 postcards, etc…Thus, the number of ways to send them postcards is

k(k-1)\ldots(k-n+1) (which is, of course, 0 if n > k).

I. iii.

This is the same as the first question but we have {k \choose 2} pairs of postcards instead of k postcards. Thus the result is ({k \choose 2})^{2}.

More later,

Nalin Pithwa

Coffee time mathematics — any number via three twos

Problem:

Here’s a witty algebraic brain teaser that had amused participants of a congress of physicists in the erstwhile USSR. The problem is to represent any number that must be positive and whole (any positive integer) using three twos and mathematical symbols.

Solution:

Let us take a particular case, and think “inductively”. Suppose we are given the number 3.  Then, the problem is solved thus:

3=-\log_{2} \log_{2} \sqrt{\sqrt{\sqrt{2}}}.

It is easy to see that the equation is true. Indeed,

\sqrt{\sqrt{\sqrt{2}}}= ((2^{1/2})^{1/2})^{1/2}= 2^{\frac{1}{2^{3}}}=2^{{2}^{-3}}.

\log_{2}2^{2^{-3}}=2^{-3} and -\log_{2}2^{-3}=3.

If we were given the number 5, we would proceed in the same manner:

5=-\log_{2}\log_{2}\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{2}}}}}.

It will be seen that we have made use of the fact that the index 2 is dropped when writing the square root.

The general solution looks like this. if the given number is N, then

N=-\log_{2}\log_{2}\underbrace{\sqrt{\sqrt{\ldots \sqrt{\sqrt{2}}}}}_{N times},

the number of radical signs equalling the number of units in the given number.

More later,

Nalin Pithwa