locus blog
Physics, Chemistry and Math!
Algebra
Math: Problem of the day-2
Dec 18th
This problem was asked in IMO 1970, Hungary.
Q: For what natural numbers 
Note that since there are 6 numbers under consideration, if a prime number 
In the set of numbers 
Therefore, there is no such
Cauchy-Schwarz inequality
Jun 10th
In this article, we’ll discuss a very powerful inequality called the Cauchy-Schwarz inequality:
Here, we’ll see how we can justify this inequality, and in another article, we’ll discuss its applications.
Proof – 1
The form of the inequality suggests that if we can somehow construct a quadratic equation where some condition can be imposed on its discriminant, we may be able to generate the required inequality.
Consider the function f (x) given by f (x) = (a1x – b1)2 + (a2x – b2)2 + ….. + (anx – bn)2
Obviously,
Note that f (x) is a quadratic expression, and if we write it in the standard quadratic form, we have
By virtue of f(x) always being non-negative, the discriminant D of f (x) must be non-positive. From this condition, the Cauchy-Schwarz inequality is immediately evident. Also, it should be obvious that the equality will hold if D = 0, which implies that f (x) has a real root, call it x0. Therefore, f (x0) = 0=(a1x0 – b1)2 + (a2x0 – b2)2 + ….. + (anx0 – bn)2
This is only possible if each of the terms on the RHS is zero:
Proof – 2
This proof involves the use of a simple result.
Prove this! This result can be easily generalized:
When does equality hold in this?
Now, we prove the Cauchy-Schwarz inequality using this result:
Its up to you to determine when the equality will hold in this case.
Proof – 3
We’ll only outline this proof briefly. If your general mathematical aptitude is good probably the first thing that should come to your mind when you look at the CS inequality is: Vectors!
Take two vectors:
Now, the dot product of two vectors will always be less than the product of their moduli (lengths):
with equality holding if the two vectors are in the same direction! Thus,
Can this result be generalized to n terms?
Probability: The Monty Hall Paradox
May 21st
<Problem taken from LOCUS Math study material>
The problem we are going to discuss is publicly one of the most well known problems in probability. This version of the problem and its solution have been taken from Wikipedia.
Suppose you are in a game show, and you’re given the choice of three doors. Behind one door is a new car; behind the others, goats. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you’ve chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you choose Door 1 and the host opens Door 3, which has a goat. He then asks you “Do you want to switch to Door 2?” Is it to your advantage to change your choice?
Figure-1
Before going through the solution, give the problem a great deal of thought. Will switching change the probability of wining? Or will it not matter because it is equally likely that the car may be behind Door 1 or Door 2 ?
O.K., now the solution. We are assuming that the player initially picked Door 1. (However, the player may initially choose any of the three doors). We’ll now calculate the probability of winning by switching, by listing out all cases explicitly.
Case 1: The car is behind Door 1. In this case, the game host Monty Hall must open one of the two remaining doors randomly
Case 2: The car is behind Door 2. Then the host must open Door 3
Case 3: The car is behind Door 3. Then the host must open Door 2
If the player chooses to switch, he’ll win only if the car is behind either of the two unchosen doors rather than the one that was originally picked.
The following diagram visually depicts the various cases and what happens with switching.
Figure-2
Let us explain how we arrived at the various probabilities using a probability tree:
Figure-3
Thus, switching leads to winning with probability 2/3 , that is, the player should switch for a higher probability of winning!
This result may seem very counter-intuitive to you. After all, you may say, the remaining two doors must each have a probability 1/2 of containing the car. However, this intuition is wrong.
In fact, you are not alone in this intuition . When first presented with this problem, an overwhelming majority of people assume that each door has an equal probability and conclude that switching does
not matter. Even Nobel laureates have been known to have given the wrong answer and to have insisted upon it! For more interesting facts about this problem, you’ll find a lot of resources online. Here’s a different version of the same problem call “The Prisoner’s Dilemma”
There are three condemned prisoners, a random one of whom has been secretly chosen to be pardoned. One of the prisoners begs the warden to tell him of one of the others who will be executed, arguing that this reveals no information about his own fate, but increases his chances of being pardoned from 1/3 to 1/2. The warden obliges, secretly flipping a coin to decide which name to provide if the prisoner who is asking is the one being pardoned. Does the warden’s answer change the prisoner’s chances of being pardoned?
Euler’s formula
Apr 30th
Most of us are familiar with Euler’s (miraculous) formula:
However, how many of us have actually given much thought to why this should hold true? Even more fundamental is the question that what meaning should be attached to raising a real number like e to a complex power iθ.
Many math authors will propose this formula as a definition. That’s very unfair to one of the greatest achievements of Euler – he certainly didn’t think up this formula in a dream. There must’ve been some logical reasoning process behind it.
This article discusses one simple “proof” of Euler’s formula, using just the exponential series expansion:
For now, lets make a leap of faith and assume that this expansion will hold for x = iθ:
One possibility is to note that A(θ) represents the (Taylor) expansion series of cos(θ), while B(θ) represents that of sinθ. However, let us not use any more expansion series, but rather proceed in a more elementary fashion.
Step – 1 :
From the series of A(θ) and B(θ), note that
But since for θ = 0, we have
Step – 2
Let us denote by Φ the argument of A(θ) + iB(θ) :
The argument of A(θ) + iB(θ) can be taken to be 0 if θ = 0. Thus, Φ = θ.
Now, carefully observe what we have proved in step – 1 and step – 2. The former says that the mysterious looking quantity e raised to the power iθ has a magnitude of unity, no matter what the value of θ, while the second step says that it has an argument of θ:
Figure-1
Therefore, its real part A(θ) must be cosθ, while its imaginary part B(θ) must be sinθ:
Our “proof” incidentally also proves the Taylor expansions of sinθ and cosθ:
In some future post, more justifications for Euler’s formula will be presented.
What’s the difference between permutations and combinations?
Apr 10th
One math topic that students find most confusing is Permutations and Combinations, and the biggest problem students face is not realizing the difference between a situation which involves permutations and one which involves combinations. Although for many people it takes time to understand this distinction, here’s an article that explains on a simple level the difference between the two concepts and which you can use as a starting point in learning this distinction.
The most important thing to remember is that
- Permutations correspond to Arrangements
- Combinations correspond to Selections
If you can make this association properly, the rest should be a breeze. The best example that comes to mind to make this association is the one outlined below:
We have a squad of 15 cricket players. Suppose that we have to form a playing team of 11 players out of these 15. Now, two cases arise:
- Just forming the team: If it is required only to decide which of the 11 out of the 15 players will be playing, then the problem is one of selection, that is, a combination problem. You only have to ascertain which 11 of the 15 players will play, which means that you have to select a playing team of 11 out the total 15 possible players.
- Deciding the team and its batting order: Now, in addition to deciding which of the 11 out of 15 players will play, you also have to decide the order in which they will bat. This is therefore, a problem of selection with arrangement, that is, it is a permutation problem.
Whenever you are in confusion regarding whether to apply permutations or combinations, thinking and visualizing of this example should help you a lot.
Let’s try it with two simple examples:
Q1. How many words of 4 letters exist?
A1. In a word, the arrangement of letters obviously matters. For example, ABCD is different from ACBD. This is a problem where we have to count the arrangements of 4 letters, that is, the permutations of 4 letters, out of the 26 possible letters in the English alphabet. The answer is therefore 26P4
Q2. From a group of 26 people, you have to send an expedition of 4 people to Mt. Everest. In how many ways can you form your team?
A2. What matters here is the combination or group of 4 people, not any order or arrangement. Your task is restricted to selecting the 4 people – you do not have to arrange them in any certain fashion. Therefore, this is a combination problem and the answer is 26C4
Reflect on the operative words “Arrangements” vs “Selections” whenever you are faced with the confusion of “Permutations” vs “Combinations”.