Wilson's Theorem for CAT

Wilson's theorem states that for any prime number 'p', (p-1)! divided by p leaves a remainder of p - 1.

In other words,
16! divided by 17, remainder is 16.
12! divided by 13, remainder is 12
10! by 11, remainder is 10

and so on.

This has an interesting extrapolation. For any prime number 'p', (p-2)! divided by p leaves a remainder of 1.
15! divided by 17, remainder is 1.
11! divided by 13, remainder is 1
9! by 11, remainder is 1

and so on.

The proof for this theorem is interesting. If we take any prime 'p', we can have two interesting observations about it

1. For any number that leaves a remainder 'a' on division by p, we can find a unique remainder 'b' on division by p such that a*b leaves a remainder of 1 on division by p. (An extrapolation of Linear Congruence Theorem)

2. For any prime p, of there is a number n such that n^2 leaves a remainder 1 on division by p, then n has to leave a remainder either 1 or -1 on division by p. The proof for this is fairly simple.

If n^2 leaves a remainder of 1 on division by p, then n^2 = kp + 1. or (n -1) (n +1) should be a multiple of p. If p > 2, then either n -1 or n + 1 has to be a multiple of p. Or, n divided by p leaves a remainder of 1 or -1 on division by p.

So, if we take (p-1)!, this is nothing but 1 * 2 * 3 * 4 * ....(p-1). Of these let us remove 1 and (p-1), the remaining p - 3 numbers can be paired up as a * b such that a*b leaves a remainder of 1 on division by p. They will be ( p-3)/2 such pairs. The product of all these pairs multiplied together will leave a remainder of 1 on division by p.

So, 1 * 2 * 3 * ......(p-1), will effectively leave a remainder 1 * 1 * (p-1) = (p -1).

Fabulous theorem. But one can almost take it for granted that the CAT will not have a question based on this theorem in the exam. This will get slotted under the category of 'too tough to be tested in CAT'.

Similarly, Fermat's Little Theorem and Euler's Phi function would also be considered too tough for CAT.

Data Interpretation - Average growth rate vs. CAGR

Growth rate, average growth rate, CAGR - these are three terms that appear frequently in exams. I am going to examine each of this with an example.

Let us say company XYZ has revenues in 5 consecutive years as follows

2011 -  Rs. 1200 crores
2012 -  Rs. 1250 crores
2013 -  Rs. 1310 crores
2012 -  Rs. 1380 crores
2012 -  Rs. 1500 crores

For the period from 2011 to 2015, we can calculate all three - growth rate, average annual growth and CAGR. Let us do each of this.

Growth rate from 2011 to 2015.
Revenues have grown from Rs. 1200 crores to Rs. 1500 crores, a growth of Rs. 300 crores. Growth rate = 300/1200 expressed as a percentage = 25%.

Average annual growth rate from 2011 to 2015
We need to calculate growth rate in each year and then compute the average of those growth rates

Year     Revenues                            growth rate

2011 -  Rs. 1200 crores
2012 -  Rs. 1250 crores                        4.2%
2013 -  Rs. 1310 crores                        4.8%
2012 -  Rs. 1380 crores                        5.3%
2012 -  Rs. 1500 crores                        8.7%

Average of 4.2%, 4.8%, 5.3% and 8.7% = 5.75%

CAGR of revenues from 2011 to 2015
The CAGR is an interesting idea. Conceptually, it is that equal growth rate, if it had been present for all 4 years that would have taken us from Rs. 1200 crores to 1500 crores. Or, if we assume some growth rate 'r' in each year that takes us from the starting point to the end point, that r is the CAGR.

So, in our question 1200( 1 + r)^4 = 1500.

How so, each year's revenues would be (1 + r) times the previous year's revenue. So, the final year's revenue would be (1 + r) ^4 of the first year's revenue.

(1 + r)^4 = 1.25

Or, CAGR = 5.73%.

Usually, CAGR and average growth rate will be reasonably close to each other. Both give a reasonable sense of how things have been. If the growth rates are wildly variant, then CAGR and average growth rate will be far apart. Otherwise they will be close to each other.

Why CAGR is often better
Imagine a stock price that jumps by 100% in year 1 and falls by 50% in the second year. Growth rates are 100% and -50%. Average growth rate would be 25%. Sounds like fantastic returns for an investor. But this is wrong. Dramatically wrong. If the stock's original price had been Rs. 20. At the end of year 1, it would have been Rs. 40, at the end of year 2 it would have been back to Rs. 20. So, the overall growth is zero. Zlich. Nada. CAGR is 0. Remember that percentages are calculated on the starting point. So, for the same change, going up will you will see a higher percentage growth than coming down. If a stock goes from 100 to Rs. 1000 it is a 900% growth rate. If it goes the other way around, it is only a 90% decline. Oops!

So, if any mutual fund manager pitches his fund to you based on average growth, ask him for the CAGR and then politely ask him to leave. :-)

How to compute CAGR using a calculator.
Let us do this with an example. If revenues from $300m to $ 369m in 4 years, what is the CAGR? 300( 1+r)^4 = 369.

(1+r)^4 = 369/300 = 1.23
(1+r) = 1.23^0.25 = 1.053.
r = 5.3%

If we go from Rs. x to Rs. y in 'n' years. x(1+r)^n = y.
(1 + r) = (y/x) ^ (1/n)

r = (y/x)^(1/n) - 1.

Now, remember, this formula will give 'r' as 0.625 or something like that. We need to think of it as 6.25%.

Let us finish with another example.
Revenues grow from Rs. 6000 crores to Rs. 8250 crores in 5 years, what is the CAGR?
8250/6000 = 1.375
1.375^0.2 = 1.06576.
Or, r = 0.06576 or 6.58%.

CAT Coaching Onlne - Links across topics in Math

Some simple interesting patterns emerge when we look across topics. Very often, thinking about these patterns helps us wind our heads around one or the other topic. In this post, we discuss a few of those links. Nothing profound, but just an outline to help remember simple ideas

Simple Interest Compound Interest and Progressions.

The amounts at the end of each year form an AP if interest is calculated on a simple interest basis, and form a GP if interest is calculated on a compound interest basis.

For instance if amount invested is Rs. 1000 and interest rate were 10%, then amount at the end of yr 1, yr 2, yr 3,.. would be Rs. 1100, 1200, 1300,...Each year's amount is previous year's amount + Rs. 100

The same amount of Rs. 1000 invested at same 10% but on a compound interest basis would give us amounts at the end of yr 1, yr 2 of Rs. 1100, 1210, 1331...Each year's amount is previous year's amount * 1.1. This is the basis for the formula for amount on principal invested in Compound Interest basis

Combinatorics - This can be linked with almost any topic
See if you can spot some idea in some other topic that is 'sitting inside' the following combinatorics questions

1. Consider a shelf that has 4 copies of a book and 3 copies of a painting. In how many ways can we select at least one article from this shelf?

2. Consider a shelf that has 4 different books and three different paintings. In how many ways can we select at least one article from this shelf?

3. In how many ways can be place 5 different toys into 3 different boxes such that all 5 toys are allotted and no box is empty?

How else these can be interpreted is given below.

1. Consider a shelf that has 4 copies of a book and 3 copies of a painting. In how many ways can we select at least one article from this shelf?
How many factors greater than 1 does the number 2^4 & 3^3 have?

2. Consider a shelf that has 4 different books and three different paintings. In how many ways can we select at least one article from this shelf?
How many non-empty subsets does the set {1, 2, 3, 4, 5, 6 7} have?

3. In how many ways can be place 5 different toys into 3 different boxes such that all 5 toys are allotted and no box is empty?
How many onto fucntions can be defined from the set {1, 2, 3, 4, 5} to the set {a, b, c}?

Weighted averages and Mixtures.
Class A has 40 students whose average mark is 40, class B has 60 students whose average mark is 50. What is the overall average? Class A has an average mark of 40 and class B has a an average mark of 50. If the overall average is 46, what is the ratio of students in class A and class B? These two questions are two sides of the same coin. Sometimes we teach one in weighted averages and the other in mixtures.

Mathematicians are supposed to love connections. There are far more powerful connections across topics than the ones I have mentioned above. It is instructive to observe even these simple connections.

Online CAT Coaching: A few interesting True/False questions from Geometry

State whether the following statements are true or false

1. A parallelogram that circumscribes a circle has to be a square
2. A trapezium inscribed in a circle has to be an isosceles trapezium
3. Orthocenter of a triangle can lie outside the triangle
4. Triangle with sides a, b and c has the relationship a^2 + b^2 > c^2, the triangle has to be acute-angled.
5. Diagonals of a parallelogram are angle bisectors of the angles of a parallelogram.

Scroll down for answers and explanation
























1. A parallelogram that circumscribes a circle has to be a square: FALSE

In a parallelogram, opposite sides are equal. In a quadrilateral, the sums of pairs of opposite sides are equal. So, a parallelogram that circumscribes a circle should have all 4 of its sides equal. Or, it should be a Rhombus; it need not be a square.

2. A trapezium inscribed in a circle has to be an isosceles trapezium: TRUE

An isosceles trapezium is a symmetric diagram. The two base angles should be equal and the two top angles should be equal. So, a trapezeium where the base angles were equal would be an isosceles trapezium.

In any cyclic quadrilateral, opposite angles would be supplementary. In a trapezium, co-interior angles between the parallel lines would be supplementary. So, if we took a trapezium ABCD with AB parallel to CD inscribed in a circle. Angle A and Angle D would be supplementary (co-interior angles). And Angle A and Angle C would be supplementary (opposite angles of a cyclic quadrilateral). Or angle B would be equal to angle C. Ergo, isosceles trapezium.

3. Orthocenter of a triangle can lie outside the triangle: TRUE

For any obtuse-angled triangle, two of the altitudes would lie outside the triangle, and would intersect at a point outside the triangle. So, the orthocenter can lie outside the triangle.

4. Triangle with sides a, b and c has the relationship a^2 + b^2 > c^2, the triangle has to be acute-angled: FALSE

Let us take triangle with sides 2, 3 and 4. 4^2 + 3^2 > 2^2. But  as 2^2 + 3^3 < 4^2, the triangle is obtuse-angled. Is a^2 + b^2 > c^2, we can say angle C is acute-angled. We cannot say all three angles are acute-angled. One can use cosine rule also for having a go at this question (though it should be considered inelegant)


5. Diagonals of a parallelogram are angle bisectors of the angles of a parallelogram: FALSE

Diagonals of a parallelogram bisect each other. They need not bisect the angles of the parallelogram. Imagine this, if we took a rectangle and studied its diagonals. if the diagonals bisected each other, the angle between diagonal and a side would be 45 degrees. Or, we would end up having a square. So, any rectangle that was not a square would have diagonals that were not angle bisectors. So, diagonals of a parallelogram NEED NOT be angle bisectors of the angles of a parallelogram.

CAT Online Coaching - Permutation and Combination, Fixing the Errors III

This post had given a series of questions with incorrect solutions. Given below are the "debugged" solutions to questions 7, 8 and 9.

7. What is the probability of selecting 3 cards from a card pack such that all three are face cards? what is the probability that none of the three is a face card? 

Given solution

Number of cards in a card pack = 52

Numbert of face cards in a card pack = 12

Number of ways of selecting 3 cards from a card pack = 52C3

Number of ways of selecting 3 face cards from a card pack = 12C3

Probability of selecting three cards such that all three are face cards = 12C3/52C3

Probability of selecting three cards such that none of the three are face cards = 1 - 12C3/52C3

Bug in the solution:

Other possibilities exist. As in, if we select three cards from a card pack, all three could be face cards, all three could be non-face cards, one could be a face card with 2 non-face cards or we could have two face cards and one non-face card. This is why we cannot use the 1 minus idea.

As a rule we can say P(A) = 1 – P(B) – P(C) if A, B and C are mutually exclusive and collectively exhaustive events. As in among them they should account for all possible events. And there should be no overlap. Creating a group of MECE equiprobable events is the most fundamentally brilliant idea in all of probability. Go on, look it up.

Correct solution:

This is simple. Probability of selecting three cards such that none of the three are face cards = 40C3/52C3

8. A die is rolled thrice. In how many outcomes will two throws be same and the third one different?

Given solution

Let the three outcomes be ABC.

'A' can take all values from 1 to 6

'B' can also take all values from 1 to 6 

'C' can take all values except A - so it has 5 possibilities

Total number of outcomes = 6 * 6 * 5 = 180.

Bug in the solution:

The given solution is actually absurd. If two throws are to be same, then if A can take values from 1 to 6 and if B were equal to A, then b can take only one value. There can be no 6 * 6 * 5

Correct solution:

'A' can take all values from 1 to 6

'B' should be equal to A --- One possibility 

'C' can take all values except A - so it has 5 possibilities

6 * 1 * 5 = 30 outcomes.

There are 30 possible outcomes when A = B but not equal to C. Likewise, we could have A = C but not equal to B and B = C but not equal to A. So, there are totally 90 different possibilities.

9. How many 7 letter words can we have in English that have two distinct vowels and 5 distinct consonants.

Given solution

Now, we know there are 5 vowels and 21 onsonants. So, we need to select 2 from these 5 and 5 from the remaining 21. Since order is important, we need to select keeping order in mind.

So, we have 5P2 * 21P5.

Bug in the solution:

In this solution we do not account for intermingling of vowels and consonants. As in, we do not count words such as BACEDFG. We account for order within vowels and order within consonants, but we do not account for order across both categories.

Correct solution:

Select without accounting for order, then arrange everything put together

So, we have 5C2 * 21C5 * 7!.