Cauchy-Schwarz inequality.

Cauchy-Schwarz inequality offers a quick solution to certain inequality problems. I myself came across at least 1 such question in last year's CAT itself, which, fortunately, having known Cauchy-Schwarz, I could solve in a matter of seconds.

Cauchy-Schwarz states that:

(x₁² + x₂² + x₃²)(y₁² + y₂² + y₃²) ≥ (x₁y₁ + x₂y₂ + x₃y₃)², for real x_i and y_j

Without wasting anytime, we will discuss some relevant problems.

For further reference on Cauchy-Schwarz inequality, follow this link.

Problem 1:

If a, b, c ,d are real numbers with a² + b² + c² + d² = 100, then what is the maximum value of 2a + 3b + 6c + 24d.

Using Cauchy-Schwarz, we can say

(a² + b² + c² + d²)(2² + 3² + 6² + 24²) ≥ (2a + 3b + 6c + 24d)²

(100)(625) ≥ (2a + 3b + 6c + 24d)²

So, 2a + 3b + 6c + 24d ≤ 250

Problem 2:

Find the least value of x² + 4y² + 9z², if x + y + z = 14

{x² + (2y)² + (3z)²}{1 + (1/2)² + (1/3)²} ≥ {x + 2y(1/2) + 3z(1/3)}² 

=> (x² + 4y² + 9z²) ≥ (x + y + z)²/{1 + (1/2) + (1/3)}²

=> (x² + 4y² + 9z²)   ≥ 196/(49/36)

=> (x² + 4y² + 9z²)   ≥ 144

Problem 3:

If x² + y² - 6x + 4y = 4, find the maximum value of 3x + 4y.

Given equation is: (x-3)² + (y+2)² = 9

Using Cauchy Schwarz, we get

[(x - 3)² + (y + 2)²][3² + 4²] ≥ [3(x - 3) + 4(y + 2]²

9 * 25  ≥  (3x + 4y -1)²

3x + 4y -1 ≤ 15

3x + 4y ≤ 16

Regards & Best Wishes,

-Angadbir

Nature of Permutations and Combinations

Pascal's Triangle.( Each number in the triangle is the sum of the two directly above it)
Source: Wikipedia.org

(a + b)² = a² + 2ab + b²

The above expression is something that everyone is familiar with. However, does it only signify a convenient method of computing the whole square of a number?

Let us bring in the context of events and probability and see what we learn.

Suppose we have an event with 2 possible results: ‘a’ & ‘b’. (eg, if the event is a toss of a coin, then ‘a’ could be the result of having obtained a heads, and ‘b’, a tails).

If we toss the coin once, the outcome is 'a' OR 'b' :- (a + b).

If we toss the coin twice, then the result is: (a+b)(a+b) 

The above mathematical expression efficiently represents the different permutation and combination of all outcomes possible.

If we revisit the equation for (a+b)², we’d see that in the RHS, each term represents different sets of combination possible, where the coefficient of each term represent the number of permutations of each combination. 

So, the end result in this case is either both heads (a.a) OR 2 combination of heads and tails occurring in different order (a.b + b.a) OR both tails (b.b).

Similarly, if we toss the coin thrice:

(a + b)³ = a³ + 3a²b + 3ab² + b³

Again, each term above on RHS represents each possible combination of results, with the additional info that it occurs 'its coefficient' no. of times

Finding the coefficients of each term is easy using Binomial expansion.

(a + b)ⁿ = C(n,0)aⁿ + C(n,1)a^n-1b + C(n,2)a^n-2b² + .... + C(n,n)bⁿ

A nice representation of these coefficients can also be done using the Pascal's Triangle. 

The little piece of knowledge in the above article is enough to give us a good perspective to solve the below example problems:

Example 1: If a fair coin is tossed 10 times, what is the probability of obtaining 2 heads and 8 tails.

All we are looking for is the coefficient of a²b⁸ in the expansion of (a+b)¹⁰ => C(10,2) or C(10,8) = 45.

Total sample space = 2¹⁰ 

Prob = 45/2¹⁰

Example 2: Find out the number of terms in the expansion of (A + B + C)²⁰

We know that each term (result set of outcomes) is a different combination of total no. of A,B and Cs. 

In each of the terms, the total no. of all of A, B and Cs = 20. 

ie, (Total As) + (Total Bs) + (Total Cs) = 20.

So the question boils down to different non-negative integral solns for: 

a + b + c = 20 

Above equation has C(22,2) solns = 231 

(Refer previous article on P&C Concept 1 for learning how to deduce this result)

Example 3: What is the sum of coefficients of all the terms in the expansion

 of (a + b + c)²⁰

In other words, the question asks for total no. of all possible results (Regardless of the permutation orders) out of an event of 3 outcomes repeated 20 times.

So the answer is nothing but: (No. of different outcomes)²⁰  = 3²⁰

To explain more, (a+b+c)²⁰ = k₁a²⁰ + k₂a¹⁹b + k₃a¹⁸bc + .... + k₂₃₁c²⁰

Where ki are different coefficients.

Here, on plugging a value of 1 to each of a,b,c leaves us with nothing but the sum of coefficients on the RHS.

Thus, sum of coefficients = (1 + 1 +1)²⁰ = 3²⁰

Example 4: Amit is standing at Point A and needs to reach Point B. The path exists as a 5*5 Grid and he can take only 1 step to the right, or 1 step front up. Amit's 1 step equals length/width of each grid cell. In how many ways can he reach Point B. 

Amit needs to take 10 steps to reach point B. Of these he needs to make 5 right steps and 5 up steps.

If, 

R -> Amit takes a Right Step

U -> Amit takes an Up step.

Then coefficient of R⁵U⁵ in (R+U)¹⁰  represents the number of ways in which he can make 5R steps and 5U Steps, thus reaching B.

Coefficient = Total ways = C(10,5) = 252

Regards & Best Wishes,
-Angadbir

P & C concept 1

Box - Ball concept 

In how many ways one can arrange

(a) 5 different balls in 3 different  boxes    --- very common in cat
(b) 5 identical balls in 3 different  boxes    -- very common in cat
(c) 5 identical balls  in 3 identical boxes    --  less likely to appear in cat
(d) 5 different balls  in 3 identical boxes    --   might appear in cat 

(a) 5 different balls in 3 different  boxes   : (This is easy one)

Each ball can go to one of the 3 boxes. So, it has 3 choices. So, it will be 3*3*3*3*3 choices for each.
So, 3^5

Thumb rule : where^what 

5 person in lift of 8 floors . 

where --> lift , what --> person --> 8^5

(b) 5 identical balls in 3 different  boxes :

It is like this:
a+b+c+d = 4
where a, b, c and d are number of balls in each  boxes .

So, 7C3 ways


Thumb rule : counting number of whole number solutions .. 

a+b+c = n --> C(n +r -1 , r-1)

(c) 5 identical balls in 3 identical  boxes    : 

5 ways: (5, 0, 0), (3, 2, 0), (4, 1, 0),(2,2,1) or (1, 1, 3)

Thumb rule : Just counting number of ways manually 

(d) 5 different balls in 3  identical  boxes   (This is calculation based..arguably toughest one of the four )

(5, 0, 0) => 1 way only 

(4, 1, 0) =>  5C4 ways
4 balls to be grouped can be chosen in 5C4 ways and remaining one in 1 way

(2, 3, 0) => 2 balls can be chosen in 5C2 ways.

(2, 2, 1) => 5C2*3c2 /2 ways 
5C2 ways to chose 2 balls and then select 2 balls in 3 in 3c2 ways .. divide by 2 for repetitive pairs .. 

(1, 1, 3) => 5C3 ways 

In total 10 + 5 + 10 + 15 + 1 = 41 ways

Thumb rule : Just counting number of ways manually and then arrange them
Please leave a comment in case of queries .. 

Cheers and good luck ! 

Set theory - Maxima and Minima

Set theory is one of the topics in quant where you can score easily if you apply logic well .. So practice is essential as far as set theory is concerned . I had a thought of writing a big article on the same today .But I remembered one particular article written by Kamal lohia  in TG . It is arguably the best article for this topic . So I am just giving the link to that article .. It should help  immensely in solving  set theory maxima and minima problems

Article link : http://totalgadha.com/mod/forum/discuss.php?d=7553

Apologies for hibernating for last three weeks ..Hemant Saar is also little busy .. Hopefully he will be back soon ..

If you guys face problem in solving any specific prob in the same topic, Please post in the comments ..

Next up : fibonacci series and combinations 

Euler’s Theorem and Remainder problems.

Leonhard Euler (1707-1783)

Euler's theorem is a key concept used in solving remainder problems. In this article, we try to understand how to apply it and also elaborate on a few applications of the totient function. If you're the kind who prefers to know the underlying concept and likes to get going directly on using it to your advantage, just read the bold statements along with the example problems. If you're the kind who likes to understand the logic behind the concepts, go ahead and read all of the article :)

To understand Euler's theorem, we first need to understand the Euler's Totient function.

Euler's Totient Function
Euler’s totient function, E[n] denotes number of positive integers that are coprime to and less than a certain positive integer ‘n’.

Such a count is not hard to deduce. Let’s take a simple example and find out Euler’s totient for 100, ie number of positive integers that are less than 100 and coprime to 100

Prime divisors of 100 are 2 and 5.

From 1 to 100, no. of integers divisible by 2 and 5 are 100/2 and 100/5 respectively.

So no. of integers less than 100 and not divisible by 2 or 5 are:-

100 – 100/2 – 100/5 + 100/(2)(5)

This can be written in simpler manner as:- 100(1-1/2)(1-1/5)

In general, for a positive integer N having prime divisors p₁, p₂, ... , p_n;

E[N] = N(1-1/p₁)(1-1/p₂)....(1-1/p_n)

Euler's Theorem:

Euler's theorem states that if P and N are positive coprime integers, then: 

Rem[P^E[N]/N] = 1
where E[N] is the Euler's totient function for N.

Note: E[N] is not necessarily the smallest power of P, such that the remainder obtained is 1 when divided by N.

Example Problem: 

Find remainder for 9¹⁰¹/125.

Soln:
E[125] = 125(1-1/5) = 100

Since 9 and 125 are coprime, Rem[9¹⁰⁰/125] = 1

Thus, Rem[9¹⁰¹/125] = Rem[9/125] = 9

Application 1: 

All positive integers coprime to 2 and 5, follow a power cyclicity of 20 in terms of their last 2 digits. 

--> Last 2 digits of a^y = Last 2 digits of a^20x+y  (for ‘a’ coprime to 2 and 5)

Last 2 digits of a number P is nothing but: Rem[P/100]

We saw earlier, that E[100] = 100(1-1/2)(1-1/5) = 40

So, for any positive integer P coprime to 100, Rem [P⁴⁰/100] = 1.

We also noted that 40 cannot necessarily be termed as the lowest power of P that leaves remainder 1.So let’s see if there indeed exists a lower exponential power as per our requirements.

100 = 4 * 25

E[25] = 20 --> Denotes that Rem[P²⁰/25] = 1

E[4] = 2 --> Denotes that Rem[P²/4] = 1. So we can safely say that Rem[P²⁰/4] = 1

Applying CRT (discussed in previous post), we can conclude : Rem[P²⁰/100]= 1

So any coprime to 100 raised to power 20 will leave remainder 01 when divided by 100.

This means that all positive integers P coprime to 2 and 5, follow a power cyclicity of 20 in terms of their last 2 digits.

Example problem: 

Find last two digits of 13¹⁹⁸²

Soln:
Since 13 is coprime to 100, it follows a power cyclicity of 20 in its last 2 digits.

So last two digits of 13¹⁹⁸² = last two digits of 13² = 69

Note: Last 2 digits for all other numbers also follow cyclicity of 20, but with a condition that a^20x+y = a^y if a^y is not a¹

Application 2:

Any digit repeated E[n] times is divisible by n, if n is coprime to 2,3 and 5.

Let K = aaaaaaaaa...... repeated E[n] times

K = a/9 (10^E[n] -1)

Since n is coprime to 2 and 5, Rem[10^E[n]/n]=1

Further, since n is coprime to 3, Rem[a/9 (10^E[n] -1)] = 0
Thus, K is divisible by n.

Example problem:

Find remainder when 33333333......86 times is divided by 13

Soln:
E[13] = 13(1-1/13) = 12

So 3333.... repeated 12(7) = 84 times is divisible by 13.

Thus, the problem reduces to Rem[33/13] => 7

Feel free to put forth any doubts/clarifications in the comments section. We'll revert back pronto :)
-Angadbir

Chinese Remainder Theorem (CRT)

CRT is one of the most handy tools that one can use to crack some complex remainder problems. Let's understand how we can use it.

CRT states that if N is divided by coprimes ‘a’ and ‘b’ and that:

Rem[N/a] = x

Rem[N/b] = y

Then we can arrive at a solution for Rem[N/ab]

We will take 2 examples for understanding this concept. The first example provides an introduction to the second one, which is the kind where we would regularly need to apply CRT.

Example Problem 1: 

Find the lowest integer N which when divided by 5 leaves a remainder of 1, when divided by 7 leaves remainder 4, and when divided by 9 leaves remainder 2.

Soln:
Rem [N/5] = 1

Rem [N/7] = 4

Rem [N/9] = 2

Putting it mathematically, we are looking for N of the following form:

N = 5x + 1 = 7y + 4 = 9z + 2 

Above mathematical representation is the essence of CRT.

By solving (which is much easier by plugging in options whilst in the exam),
we get N = 11 for (x,y,z) = (2,1,1)

• There are greater values of N possible which would yield similar remainders when divided by 5, 7 and 9. 
• These can be found out by adding multiples of LCM(5,7,9) = 315 to 11. For example 11 + 315 = 326 is the next such number. 
• This fact is utilized more extensively in the next example problem, where we are given one such large number to start with but are asked (in a manner) to find out the smallest possible one.

Example Problem 2: 

Find the remainder when 3¹²⁰ is divided by 105

Soln:
105 = 3 * 5 * 7

If we can find the remainders obtained when 3¹²⁰ is divided by 3, 5 and 7 respectively, we can apply CRT to find the overall remainder as below:

Rem [3¹²⁰/3] = 0

Rem [3¹²⁰/5] = Rem[9⁶⁰/5] = Rem[-1⁶⁰/5] = 1

Rem [3¹²⁰/7] = Rem[9⁶⁰/7] = Rem[2⁶⁰/7] = Rem[8²⁰/7] = 1

• R = 3x = 5y + 1 = 7z + 1
• It is important to note that R = 3¹²⁰, for a particular set of (x,y,z). However, this set does not yield the smallest value for R. As we observed earlier, larger values for R are obtained by adding multiples of 105 to the smallest value for R.
• So in finding the smallest possible R of the above given form, we are in essence finding out R = Rem[3¹²⁰/105]

By carefully introspecting the above 3 points, it is not difficult to understand how CRT really works.

By solving, we get R = 36 for (x,y,z) = (12,7,5)

Thus, Rem[3¹²⁰/105] = 36

Note: In the above example and the definition given for CRT in the beginning of the article, the smaller individual divisors are taken to be coprimes to each other. For our objective, this is required for redundancy purposes but need not always be necessarily mandatory while solving using CRT.


-Angadbir

Divisibility Rules

This is one of the important concept of number system .Questions on remainders and factor are quite frequent in CAT these days . Lets see the divisibility rule of few numbers.

We all perhaps know what is the divisibility rule of 2,4,6,8,3,9 .But do everyone know the logic behind it ? 

First case :

Let me start from divisibility of 2
 

If last digit is divisible by 2 , then it is divisible by 2 ...

why ?
 

Last digit is nothing but divide by 10 ...10 is perfectly divisible by 2..
 

Now we can extend this  for 4 ..

lets take last digit --> divide by 10 -->  10 /4 --> Not perfectly divisible

Now move to next digit--> divide by 100

100 is perfectly divisible by 4 .. So divisibility rule of 4 is last two digits to be divisible by 4
 

Now this goes on ... jus try for various numbers like 8 ,16,32

the above logic works for factor of 10^n  like powers of 2 and 5 . Other numbers can't be treated this way

Second case
 

Lets take an example of next number .. take 3

10/3 --> not divisible

100/3 --> not divisible

1000/3 --> not divisible and it goes on ..

But in all three cases , the remainder is 1 .

If remainder is 1 , add the digits

Divisibility rule of 3 will add the digits and then check if its divisible by 3  . This is applicable for numbers which leaves remainder 1 when 10^n is divided by that number

Quick divisibility rule :

Take 33 :

100/33 leaves remainder 1 . So one can frame divisibility rule of 33 as sum of digits taken two at a time from the right hand side of number .

Eg . Is 2112 divisible by 33 ?

12 + 21 = 33 . 33/33 perfectly divisible . Yes .. isn’t that easy ?

Third case :

Lets take an example of next number .. take 7

10/7 --> not divisible but remainder is not 0 or 1 or -1

100/7 --> not divisible but remainder is not 0 or 1 or -1

1000/7 --> not divisible but remainder is -1

so every three digit we will have -1 remainder ..

if 10^3 has -1 remainder , 10^6 has 1 as remainder...

so its alternative in nature for every three digits .

Divisibility rule of 7 will difference of sum of  the digits taken at three at a time alternatively from RHS of the number  and then check if this resultant divisible by 7

say number is 123130 to check for divisibility by 7 .,..

so according to this concept we have , 130 - 123= 7 which is divisible by 7

Or let’s say 7123130 -- > (130 + 7) – 123 = 14 which is divisible by 7

The beauty of this method is it works well for big number divisors (for instance- 143) .

235378/143 .. is it divisible ?

10^3 / 143 = remainder is -1

By this method ,we can say 378 - 235 = 143.. 143 / 143 is perfectly divisible .That's all you r done

Applying this formula , we can test divisibility of 2,3,4,5,7,8,9,11,27,13,33,37,99,77,143,259(37*7)   etc ....

Just work on these lines .. You can easily find the divisibility of all above numbers

Ps : Feel free to revert me back in comments if you have any doubts .