Discrete Math 101: Fun with Combinatorics – 2

3.

Our task is to select a team of k players from among n players. Now, we have 2 options – Either select player 1 to be part of the team, or leave him out of the team.

If we select player 1 to be part of the team, our task is reduced to selecting players from among players.

And if player 1 is not part of the team, our task is reduced to selecting players from among players.

Hence we have the above result.

———

4.

Again our task is to select a team of k players from among n players – .

If is part of the team: We can select such a team in ways.

If is not part of the team, and is part of the team: The problem is reduced to selecting k-1 players from among n-2 players.

If and are not in the team, and is in the team: The problem is reduced to that of selecting k-1 players from among n-3 players.

Proceeding in this manner, we get the above result.

———–

5.

Again, we have n players at our disposal from among whom we wish to select a team of k players.

Say we select to be the 1st player in our team. (Note that the term “first” actually means nothing since we wish to select a “set” of objects and not an “ordered list”. However the usage of such terminology is useful for the purposes of exposition.)

Now, all we need to do is to select players from among players.

Now, let’s go back a step. What if we select to be the 1st player of the team, and select the remaining players for the team in ways.

We can see that we have n choices for the 1st player of a team.

Hence, we can select a team of k players in .

But again some teams are being repeated.

Given a fixed team, say T, we select that team k times (with each of the k players in the team being selected as the 1st player of the team). Hence we need to divide the previous result by k.

Hence we get the above result.

———-

Discrete Math 101 : Fun with Combinatorics -1

is the number of ways we can select k items from a group of n items. Say the number of players in India’s world cup squad is 14. Only 11 players can play in any particular match. Hence, on match-day, the coach has possibilities for selecting a team of 11 players from his squad. (Of course, such a situation is simply a theoretical conjecture, and no sane coach would actually list down each of possible teams and pick one from among them.)

We can easily derive some interesting results using the above meaning of .

1.

Our task is to select a team of k players from among n players. We can do this by directly selecting which players are to be part of the team, or by selecting which players are to be left out, giving the above result.

2. =

Look at it this way. We have n players, say , and we want to select a team of k players from among them.

Let us select the players one by one.

For selecting the first player, we have n possible options.

Now having selected one player, we have n-1 possible options for selecting the 2nd player.

Similarly, given that we have selected i players, we have n-i options for selecting the i+1 th player.

Thus, we get that we can select k players from among n players in ways.

But wait!

There are many repetitions in the teams of 11 players that we selected. Consider any particular fixed team of k players. That team is selected by us in ways.

Therefore, we have: .

——-

Note that given a list of k items, we can have k! permutations of those items. (This can be easily derived recursively.)

——-

Probability – Monty Hall problem

Our friend Monty Hall is a game show host. Every week he asks one person from his audience to come onto the stage. On the stage are 3 closed doors. Behind one is a brand new car, and behind the other 2 are goats. The car is equally likely to be behind any of the 3 doors. The contestant selected from the audience obviously wants to win the car.

Monty Hall explains the rules of the game to the contestant — In front of you are 3 closed doors. Behind one of them is a car, and there are goats behind the other 2. I know what is behind each door. Your first task is to select a door.

Our contestant selects door 1.

—-

Monty now again starts expounding on probability — You have selected door 1. Now, I will select either door 2 or 3 to open. Note that I know what is behind each of the doors. I will decide which door to open based on the following rules:

- If door 2 has a car behind it, I will open door 3.

- If door 3 has a car behind it, I will open door 2.

- If neither of the above conditions hold true, i.e. both doors 2 and 3 have goats behind them, I will randomly select one among these 2 doors with probability 0.5 and open that door.

—-

Now, having explained thus to our contestant, the omniscient Monty goes and opens door 3, and reveals to the world (including our contestant) the goat standing behind it.

—-

Now, Monty turns to the contestant for the endgame and speaks thus — As you can can see, door 3 has a goat behind it. Doors 1 and 2 are still closed. Whichever door you select, you will get whatever is behind that door. You can either decide to stay with your original choice i.e. door 1, or you could decide to switch i.e. select door 2. What do you want to do — stay or switch?

As the music in the recording studio rises to a crescendo, our dear contestant is faced with this question on probability to answer. What should he do?

————

At first glance, it does seem that it is immaterial as to what the contestant chooses. One could argue that there are 2 doors (doors 1 and 2) one of them having a goat behind it, and the other having a car behind it. The car is equally likely to be behind either of the 2 doors. So, the contestant could as well flip a fair coin, and choose which door he wants to go with.

—-

However there is a flaw in the above reasoning.

– The probability that there is a goat behind door 1 is 2/3, and the probability that there is a car behind door 1 is 1/3.

To see why this is so, consider the following argument — Initially there were 3 doors. Two of them had goats behind them and one of them had a car behind it. Door 1 was one among these 3 doors. Therefore, the probability that door 1 has a car behind it is 1/3 and the probability that it has a goat behind it is 2/3.

Now, you could argue against the above explanation this way : ” What you said about the probability of a car being behind door 1 being 1/3, and that probability of a goat being behind door 1 being 2/3 was true initially, and not after Monty went and opened door 3, and showed everyone the goat standing behind it. Once Monty did that, we were left with 2 doors, and 1 goat and 1 car, and hence the probability that there is a car behind door 1 is 1/2 and the probability that there is a goat behind door 1 is also 1/2.”

But again, the argument that you presented above is not wholly correct. We can see it this way — we agree that initially i.e. before Monty opened door 3 and showed a goat behind that, the probability of these being a car behind door 1 is 1/3. My claim is that this remains the same even after what Monty did.

To better understand that, consider the following situation —

Assume that there are 100,000 doors instead of just 3. Also, behind 99,999 of these doors are goats and behind a single one is a car. The car is equally likely to be behind any of the 100,000 doors. So, what we have here is a 100,000-door version of Monty’s 3-door problem.

Now, you select a door, say door 385.

Now, Monty has been asked to open 99,998 doors, i.e. he has been asked to keep 2 doors closed. It is also specified in the rules that one of these closed doors should be door 385 since that was the one you selected. Further, Monty knows what is behind each of the doors, and Monty has been specifically instructed that the 99,998 doors that he opens should all reveal goats behind them.

So Monty goes and opens 99,998 doors. He leaves door 385 and one other door, say door 6724 closed. Now, as we said earlier, behind each of the 99,998 doors that Monty opened, was a goat.

Now, what do you think is the probability that there is a goat behind your selection door 385?

It is 1/100,000 and not 1/2.

The reason as to why door 385 remained closed even when just 2 doors remained (i.e. 385 and 6724) was because Monty had been instructed not to open 385 as part of the rules.

There is 1/100,000 probability that door 385 contained a car behind it, and Monty selected door 6724 uniformly at random from the remaining 99,999 doors for keeping closed. In such a situation, staying with your original selection (i.e. door 385) would win you the car.

However, it is much much more likely (99,999/100,000) that your initial selection (385) had a goat behind it, and that Monty knowing that 6724 had a car behind it, opened the remaining 99,998 doors. In this situation, switching (i.e. selecting door 6724) would get you the car.

—-

Coming back to our 3 door version, we can argue that switching would win you the car with probability 2/3, while staying with your original selection would get you the car with a probability of 1/3.

Hence, one who has a working knowledge of probability should advise the contestant to switch.

Greed, and love of dear life: The Pirate Problem

There are pirates discussing on how to divide their booty of 100 gold coins. The pirates have a strictly defined seniority order among themselves. Let’s say that, for all i, Pirate i is more senior than Pirate j, for all j < i.The method that they agree upon to divide their loot is the following:-

—-

Initially there are n pirates.

i = n;

While (there is a pirate alive)

Pirate i proposes a division.

If (at least 50% of the pirates alive approve of his division plan)

Division takes place, and things end here.

Else

Pirate is killed (and of course, the division proposed by him is not carried out).

i – -;

End of While loop.

End of algorithm.

—

We also have a few other observations to make:

1. The pirates value their own individual lives most of all.
2. Next to protecting their lives, the thing uppermost on their minds is to maximize their own share of the loot.
3. The 3rd most important consideration for the pirates is to reduce the number of pirates on board.
4. All pirates are extremely intelligent (and thus, each certainly knows that, each of the others is extremely intelligent).
5. Whenever pirates have to make a decision (whether to approve/ disapprove of, or to propose a division plan), they keep in their minds the 4 points mentioned above.

Question: Say, n = 5, what division should the senior-most pirate propose (he is the one who gets the first chance to propose a division plan) so as to ensure that he doesn’t get killed, and given that he doesn’t get killed, to maximize his share of the loot?

Solution.

Consider what would happen with just one pirate. Obviously, he would get all the 100 coins.

With 2 pirates, Pirate 2 gets to propose a division. He knows that he will always get 50% of the vote (by approving of his own plan), and hence can propose freely any division that he likes. Hence, he will propose a division with 100 coins for himself, and none for Pirate 1, and get away with it.

With 3 pirates, Pirate 3 has to decide on how to divide the loot. He knows that if he dies, only 2 pirates would be left. In such a scenario, we all know that Pirate 1 will not get any coin. Hence, Pirate 1, being greedy, has an incentive to accept any plan that Pirate 3 proposes giving him > 0 gold coins so as to ensure that Pirate 3′s division plan is carried out. Hence, Pirate 3 can win 2 votes (out of 3) by proposing a division giving 1 coin to Pirate 1 and keeping 99 for himself.

With 4 pirates, Pirate 4 gets to decide the division scheme. Again, we know that, if Pirate 4 dies, Pirate 2 wouldn’t get even one gold coin, in the subsequent division which would be proposed by Pirate 3. Hence, Pirate 4 can win 2 votes (out of 4) by proposing a division giving 1 coin to Pirate 2, and keeping 99 for himself.

With 5 pirates, it is Pirate 5 who gets to propose. Again, his death would result in Pirate 1 and Pirate 3 not getting anything in the subsequent division which would be proposed by Pirate 4. Hence, to win their votes, and get 3 votes (out of 5), Pirate 5 can give 1 coin each to Pirates 1 and 3, and keep 98 for himself.

—-

Generalizing for n (n < 100):-

Pirate n can propose a division giving 1 coin each to Pirates n-1, n-3, … (up to either 1 or 2), and keep the rest for himself.

—-

A beautiful proof

There are some proofs, for which the very fact of being acquainted with the working of the mind which came up with such beautiful ideas can transport you to a state of ecstasy.

Georg Cantor (1845-1918) gave a beautifully simple proof for proving that the power set of the set of natural numbers (N) has “more” elements than the set N itself, i.e. 2^N is uncountably infinite.

Assume to the contrary that 2^N is countably infinite. In other words, there exists a bijection between the set N and the set 2^N. (This is what is meant by a set S being countably infinite, i.e. if a set S is countably infinite, then there exists a bijection between S and the set, N of natural numbers.)

2^N = {R_0, R_1, R_2, … }  [R_0, R_1 etc are elements of 2^N i.e. subsets of N.]

Assuming that 2^N is countably infinite implies that every element of 2^N is equal to R_i for some i \in N.

Now, consider this set. Call it D.

If  0 \in R_0, then 0 \notin D.
Else if, 0 \notin R_0, then 0 \in D.

Similarly, deciding whether or not each i \in N belongs to D, is done based on whether or not i belongs to R_i.

If R_i contains i, then we do not include i in D.

And if R_i does not contain i, then we include i in D.

What do we get now?

We get a set D that is different from each R_i. (It is different from R_5 in whether or not ’5′ is contained in it; it is different from R_345 in whether or not ’345′ is contained in it. Hence, D can not be equal to set R_5. And, D can not be equal to set R_345.)

So, we see that D can not be equal to any of the sets R_i.

But, D is also a subset of N.

Hence, D should ideally be an element of the power set of N. By assumption, 2^N = {R_i : i \in N}.

We just saw that D can not be equal to any R_i.

Hence D is NOT a part of 2^N.

This is a contradiction!

We are done. 2^N can not have a bijection with N. 2^N is uncountably infinite.

Extended Longest Path problem

These are slides from a talk on the Longest Path Problem at the Penn State Theory seminar.

Talk_longest path

In the Longest Path Problem, we are given an undirected graph, G =(V,E), and integer , and are asked to find out whether or not there exists a simple path of length k in G.

The Extended Longest Path Problem is a variant of the above. Here, we are asked to find out all pairs of vertices that have a simple path of length k between them.

Longest Path: Method of Random Orientations

In this post, we shall consider an NP-complete problem, namely that of determining whether a simple path of length k exists in a given graph, G = (V,E).

Formally,

LONGEST PATH PROBLEM

Input: undirected graph, G = (V,E), integer .

Parameter: k

To find: Does G contain a simple path of length, k?

Vertex Cover and Set Cover – 4

Question: We are given an instance of the Vertex Cover problem. We are also given an algorithm for the Set Cover problem. Using this algorithm as a black box, solve the given instance of the Vertex Cover problem.

Solution:

Given instance of Vertex Cover problem: undirected graph, G = (V, E); positive integer k.
Question: Does G have a vertex cover of size at most k?

===

Vertex Cover and Set Cover – 3

Consider the Vertex Cover problem.

To recapitulate:
Given: Undirected graph, G = (V, E), positive integer, k.
Question: Does G have a Vertex Cover of size at most k?

Now, we shall look at a problem related to the above question.

How do we verify the validity of a answer to the Vertex Cover problem?

Vertex Cover and Set Cover – 2

Having looked briefly at the Vertex Cover problem, here we shall define the Set Cover problem.

As the name suggests, we have a set, and we need to “cover” something.

Consider the following example:

We have a set of cities, S = {Madras, Delhi, Pilani, Los Angeles, London, Paris}.

Vertex Cover and Set Cover – 1

Here we will look at two very interesting problems. One is known as the Vertex Cover Problem, and the other as the Set Cover Problem. Both are quite simple to define, and visualize (and equally difficult to solve efficiently ).

Let us consider the Vertex Cover Problem first. As the name suggests, we have to “cover” something. We are given an undirected graph, G = (V, E). We need to select a set of vertices from V, so that all edges are “covered” by this set of vertices.

What exactly do we mean by covering? A vertex “covers” all edges that are incident upon it. This does seem to be quite a natural definition.

Life of Srinivasa Ramanujan

It is one of the most romantic stories in the history of mathematics: in 1913, the English mathematician G. H. Hardy received a strange letter from an unknown clerk in Madras, India. The ten-page letter contained about 120 statements of theorems on infinite series, improper integrals, continued fractions, and number theory (Here is a .dvi file with a sample of these results). Every prominent mathematician gets letters from cranks, and at first glance Hardy no doubt put this letter in that class. But something about the formulas made him take a second look, and show it to his collaborator J. E. Littlewood. After a few hours, they concluded that the results “must be true because, if they were not true, no one would have had the imagination to invent them”.

Thus was Srinivasa Ramanujan (1887-1920) introduced to the mathematical world. Born in South India, Ramanujan was a promising student, winning academic prizes in high school. But at age 16 his life took a decisive turn after he obtained a book titled A Synopsis of Elementary Results in Pure and Applied Mathematics. The book was simply a compilation of thousands of mathematical results, most set down with little or no indication of proof. It was in no sense a mathematical classic; rather, it was written as an aid to coaching English mathematics students facing the notoriously difficult Tripos examination, which involved a great deal of wholesale memorization. But in Ramanujan it inspired a burst of feverish mathematical activity, as he worked through the book’s results and beyond. Unfortunately, his total immersion in mathematics was disastrous for Ramanujan’s academic career: ignoring all his other subjects, he repeatedly failed his college exams.

As a college dropout from a poor family, Ramanujan’s position was precarious. He lived off the charity of friends, filling notebooks with mathematical discoveries and seeking patrons to support his work. Finally he met with modest success when the Indian mathematician Ramachandra Rao provided him with first a modest subsidy, and later a clerkship at the Madras Port Trust. During this period Ramanujan had his first paper published, a 17-page work on Bernoulli numbers that appeared in 1911 in the Journal of the Indian Mathematical Society. Still no one was quite sure if Ramanujan was a real genius or a crank. With the encouragement of friends, he wrote to mathematicians in Cambridge seeking validation of his work. Twice he wrote with no response; on the third try, he found Hardy.

Hardy wrote enthusiastically back to Ramanujan, and Hardy’s stamp of approval improved Ramanujan’s status almost immediately. Ramanujan was named a research scholar at the University of Madras, receiving double his clerk’s salary and required only to submit quarterly reports on his work. But Hardy was determined that Ramanujan be brought to England. Ramanujan’s mother resisted at first–high-caste Indians shunned travel to foreign lands–but finally gave in, ostensibly after a vision. In March 1914, Ramanujan boarded a steamer for England.

Ramanujan’s arrival at Cambridge was the beginning of a very successful five-year collaboration with Hardy. In some ways the two made an odd pair: Hardy was a great exponent of rigor in analysis, while Ramanujan’s results were (as Hardy put it) “arrived at by a process of mingled argument, intuition, and induction, of which he was entirely unable to give any coherent account”. Hardy did his best to fill in the gaps in Ramanujan’s education without discouraging him. He was amazed by Ramanujan’s uncanny formal intuition in manipulating infinite series, continued fractions, and the like: “I have never met his equal, and can compare him only with Euler or Jacobi.”

One remarkable result of the Hardy-Ramanujan collaboration was a formula for the number p(n) of partitions of a number n. A partition of a positive integer n is just an expression for n as a sum of positive integers, regardless of order. Thus p(4) = 5 because 4 can be written as 1+1+1+1, 1+1+2, 2+2, 1+3, or 4. The problem of finding p(n) was studied by Euler, who found a formula for the generating function of p(n) (that is, for the infinite series whose nth term is p(n)xⁿ). While this allows one to calculate p(n) recursively, it doesn’t lead to an explicit formula. Hardy and Ramanujan came up with such a formula (though they only proved it works asymptotically; Rademacher proved it gives the exact value of p(n)).

Ramanujan’s years in England were mathematically productive, and he gained the recognition he hoped for. Cambridge granted him a Bachelor of Science degree “by research” in 1916, and he was elected a Fellow of the Royal Society (the first Indian to be so honored) in 1918. But the alien climate and culture took a toll on his health. Ramanujan had always lived in a tropical climate and had his mother or his wife to cook for him: now he faced the English winter, and he had to do all his own cooking to adhere to his caste’s strict dietary rules. Wartime shortages only made things worse. In 1917 he was hospitalized, his doctors fearing for his life. By late 1918 his health had improved; he returned to India in 1919. But his health failed again, and he died the next year.

Besides his published work, Ramanujan left behind several notebooks, which have been the object of much study. The English mathematician G. N. Watson wrote a long series of papers about them. More recently the American mathematician Bruce C. Berndt has written a multi-volume study of the notebooks. In 1997 The Ramanujan Journal was launched to publish work “in areas of mathematics influenced by Ramanujan”.

(This biography of this awe-inspiring genius is taken from here.)

Interesting questions

Here are two simple and interesting ideas.

1. A group of ‘n’ persons are in a classroom. Prove that there always exist two people having the same number of friends.

(Note that if ‘a’ is a friend of ‘b’, then ‘b’ is also a friend of ‘a’.)

This can be easily proved using a principle known as the Pigeon Hole Principle.

This basically states that if we have larger number of pigeons and a lesser number of holes, then there will be at least one hole with more than one pigeon. Quite simple.

Returning to the question, assume there is at least one person in that group who is a friend of everyone else. This implies that there does not exist any person having zero friends. (Since every person has at least one friend- the one who is the friend of everyone else.)

So, what are the possible values for the number of friends any person in the group can have?

1, 2, 3, …., n-1. (As we observed above, value zero is not possible here. )

Now, what are the total number of persons in the group?

n.

So, we have ‘n’ persons, to each of whom we need to assign a value (number of friends that person has). We can assign values from a set of only ‘n-1′ possible values.

Hence, there will be at least two persons having the same number of friends, for the case that there is at least one person who is a friend of everyone else.

Now, what if there is no person having ‘n-1′ friends?

In this case, the set of values indicating the possible number of friends a person can have, does not include value ‘n-1′.

(The set of values is: {0, 1, 2, …, n-2} )

The same argument as above applies here. Hence proved.  QED

Point to ponder:

It was stated earlier that: If ‘a’ is a friend of ‘b’, then ‘b’ is also a friend of ‘a’. Question: Where has that fact been used in the above proof?

2. A group of ‘n’ friends live in a hostel. Let us name the friends as 1, 2, 3, …, n. Each one has a room assigned to him/her. (Person 1 is assigned Room 1; Person 2 is assigned Room 2, and so on.) There are ‘n’ rooms in all- one for each person.

One day, on coming back to the hostel after a trip, they decide to randomly enter whichever room they wish to. For instance, Person 1 enters Room 5; Person 2 enters Room 3; and so on (keeping in mind that only one person can enter any given room.)

Question: What is the expected number of persons who entered their assigned rooms?

Randomly entering a room (keeping in mind that only one person enters any given room) corresponds to a random permutation of  1, 2, …, n.

In other words, randomly re-order the sequence 1, 2, …, n.

For example (n= 5 ), we get 3, 5, 1, 4, 2. Here , Person 3 enters Room 1; Person 5 enters Room 2; and so on.

Now, what is the probability that Person 1 enters Room 1?

Answer: 1/n. (Since he has ‘n’ rooms to choose from.)

Let us define a few random variables which will help us in computing the expected value.

Let be a random variable that has value = 1 if Person ‘i’ enters Room ‘i’, and value = 0, if Person ‘i’ does not enter Room ‘i’.

We need to find the expected number of persons in their assigned rooms. This is the same as: .

Let us compute .

 =      Pr[Person 'i' enters Room 'i'] x [Value of for this event]  +  Pr[Person 'i' does not enter Room 'i']  x [Value of   for this event]

= (1/n) x 1 + (n-1)/n x 0

= 1/n.

(Notation: E[X] denotes Expected value of random variable X; Pr[e] denotes probability that event ‘e’ occurs.)

Now, we will use a technique called “Linearity of Expectation“. What this says is that if we have two random variables, X and Y, then E[X + Y] = E[X] + E[Y]. (This can be extended to any number of random variables, not just two.)

(Now, if X and Y are independent random variables (i.e. Y’s value does not depend on what the value of X is; and vice versa), then it is intuitively clear that the expectation of the sum should equal the sum of expectations. But the powerful idea behind the principle of Linearity of Expectation is that this holds even when the random variables are not independent.)

Coming back to the question:-

We can apply Linearity of Expectation to solve the problem.

= .

Therefore, = 1/n + 1/n + … + 1/n = 1

In other words, the expected number of persons who will enter their assigned rooms is one.

——–

As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality. – Albert Einstein

——–

How wonderful that we have met with a paradox. Now we have some hope of making progress. -Niels Bohr

Bipartite Matching: An application

Firstly, we define the concept of a matching.

Suppose we are given a graph, G = (V, E). As the name suggests, a matching means a pairing of vertices of the graph. In other words, each vertex is “matched” to exactly one other vertex in the graph to which it had been connected by an edge in E. We say that such edges, which “match” two vertices with one another, are part of the matching.

Formally, a matching is a set of edges, such that no two edges in S are adjacent to each other. (Two edges are adjacent if share a common end-vertex.)

Example:

Matching Example : Bold edges {(1,2), (4,5)} form a matching.

Maximum matching:

A matching of maximum cardinality is called a maximum matching. (Note that a graph may have more than one matching of maximum cardinality.)

Example:

{ (1,2), (3,4), (5,6) } form a maximum matching

Clearly, we can not get a matching having more than 3 edges for the above graph. (There are only 6 vertices; for each pair of vertices there can be at most one edge in the matching; hence there can not be a matching with greater than 3 edges.) Hence, this is a maximum matching.

Perfect Matching:

We were able to pair up all vertices of G in the above example. Such a matching is called a perfect matching.

A perfect matching may not exist for many graphs.

Example:

Maximum matching is of size one. Two vertices are unpaired in maximum matching.

If the graph we consider is a bipartite graph, then the matching in such a graph is termed as a bipartite matching.

Practical application of bipartite matching: Job recruitment process

Suppose there are ‘n’ companies competing to hire students from a university, and that ‘m’ students are available for hiring. Assume that each company has only one job opening, and hence can hire at most one student.

After the tests and interviews, each company shortlists certain candidates. The company sees no distinction among its shortlisted candidates, and is willing to hire any one of them to fill its opening.

It is clear how this is a problem of bipartite matching.

Let L be the set of companies, and R be the set of students.

An edge exists between, and if r is one of the candidates shortlisted by the company.

Each company can hire at most one (by our assumption; either it hires a student, or goes home empty-handed.)

Quite obviously, each student can work in at most one company (either the student is selected by one company; or goes home empty-handed.)

Hence, this is a clear case of bipartite matching between the set of companies and the set of students.

The university would certainly like to find out the maximum number of students who can get placed through this recruitment process.

In other words, the university wishes to find out the size of the maximum bipartite matching possible for the company-student graph.

There exist polynomial time algorithms for computing a maximum bipartite matching. Hence, the problem can be solved by running any of those algorithms on the given instance of the company-student graph.

Points to ponder:

1. When does a bipartite graph have a perfect matching? What is the common structure of such bipartite graphs, which enable them to have a perfect matching? In particular, there is a very interesting theorem known as Hall’s Marriage Theorem. The theorem has two parts to it: an “if” part, and an “only if” part. One of these is simple to visualize, while the other is somewhat non-intuitive. You could read up on that.

2. There is a concept of maximal matching.

A maximal matching of a graph G = (V, E) is a matching to which no other edge of E can be added without violating the matching property. (Matching property requires that all edges of a matching be non-adjacent.)

Example:

Maximal matching: No edge can be added to the matching { (1,6), (3,4) } without violating the matching property.

The size of this particular maximal matching of G is 2. (Unlike maximum matchings of a graph which are all of the same size, the maximal matchings of a graph can be of different sizes.)

But we can certainly do better than this in terms of getting a matching of higher cardinality.

A Maximum matching for G: { (1,2), (3,4), (5,6) }

(You can also observe that the above matching is also a perfect matching of G (all vertices are paired).)

Question: Can you find a relation between the size of a maximal matching and the size of a maximum matching. Let be the size of a particular maximal matching, and let denote the size of any maximum matching (all maximum matching are, by definition, equal in size).

We know that .

Claim: There exists a constant factor,, such that , for all possible .

(Notes: How can we get a matching of greater size using a given maximal matching? Clearly, we can not add an edge to it (by definition of maximality, the resultant set will not be a matching.)  So, we need to remove an edge from the maximal matching. Suppose we remove a particular edge, . We are, in effect, freeing two vertices, and , which are available to be paired up with some other free vertices. Hence, on removing one particular edge from a maximal matching, we can hope to add at most two new edges in its place. This suggests that the size of a maximum matching is at most twice the size of a maximal matching (i.e. k = 2).

I’m not sure about the correctness of the above explanation, as it omits certain details, and may not be rigorous in terms of exploring all possible alternatives for building a maximum matching. On an informal level, this explanation might suffice.)

Birthday Paradox

In a group of 23 people, the probability that two or more people will share their birthdays is greater than 50%. For a group of 57 people, this probability increases to 99%.

This may seem counter-intuitive at first sight. There are 365 possible days on which a birthday can occur. So it may seem odd that in a group of 57, there is 99% probability of a shared birthday.

Question: In a group of ‘n’ people, what is the probability that any of those ‘n’ persons shares a birthday with any of the others in the group?

This is very simple.

The answer is simply:

1 – (364/365) (363/365) … ((365 – n + 1 )/365 )

=   365 !  / [ (365^n) (365 - n)! ].

Approximating this function, and plugging in values of n, we get the probability of a group of those many people having a common birthday in their midst.

See http://en.wikipedia.org/wiki/Birthday_paradox for more on this.

Does Kruskal produce all MSTs?

The area of Theoretical Computer Science has so many beautiful questions. Among these are a few questions, that can be called as “cute” questions. The problem raised here is one such question.

Here’s the question: Given a weighted connected graph, G, does Kruskal’s algorithm produce all possible Minimum Spanning Trees of G?

A couple of lines on Kruskal’s algorithm: In order to find the MST, you take the edges and order them in non-decreasing order. Then traverse this sorted sequence of edges, picking edges one by one, keeping in mind that the picked edge should not create a cycle with any of the previously picked edges.

There’s also another interesting fact about MSTs: If a graph has unique edge weights, i.e. no two edge weights are same, then that graph also has a unique MST. Also, if a graph has repetitions of certain edge weights, then there may exist more than one MST for the graph.

Now, back to the original question.

Let us take an example graph to understand the arguments that follow.

Suppose our connected graph, G has the following ordered sequence of edge weights:

1 (e1), 2 (e2), 3 (e3), 4 (e4), 5 (e5), 5 (e6), 5 (e7), 6 (e8), 7 (e9), 8 (e10), 8 (e11), 8 (e12), 8 (e13), 9 (e14), 10 (e15), …. , (em).

(The parenthesized symbols are the edge names)

Now, we apply Kruskal’s algorithm on G to get some MST. Let’s call this as Tk.

Also, let T be any random MST of G. We shall compare T with Tk to see whether T can be produced by Kruskal’s algorithm.

Simple till now, right?  :)

Now, T and Tk will generally have some common edges. (Even if they don’t the ensuing arguments will hold just as well.)

Let us consider the edges one by one (in sorted order). Let’s say that edge, e1 is part of both T and Tk. Similarly, edges, e2 and e3 are both of both T and Tk. Also, let us assume that edge, e4 is not part of either T or Tk. So far so good; all edges thus far between T and Tk are common.

Case 1: Now, let us assume that Tk contains edge, e5, but not e6; while T contains edge, e6, but not e5.

We now have to prove that Kruskal’s algorithm can produce an MST which contains e6 but not e5.

(We know that Kruskal’s algorithm selects an edge to be a part of the MST in sorted order. When two or more edges have equal weight, it randomly picks one of them and checks whether that edge can be a part of the MST. Only then does it go to the next edge of equal weight to test whether that is compatible with the tree constructed thus far.)

So, in our example, after Kruskal’s algorithm successfully processes edge, e4, it has to make a choice between e5 and e6. Let us suppose that it picks edge, e6. We know that e6 would be compatible with the previously made selections of e1 through e4 (this is because, T contains the same selection as Kruskal for e1 through e4, and also contains e6. Hence, e6 is compatible with the earlier selections i.e. it does not form a cycle with those edges).

So, one problem is sorted out. There does exist a Kruskal-produced MST, call it Tk1, having edge, e6. But, we need to ensure that this MST does not contain e5. This can be easily proved.

Here’s the proof: We know that  { e1, e2, e3 } is compatible with both e5 as well as e6. (e4 is part of neither T nor Tk, in our example). Now, Kruskal’s algorithm always tests an edge along the ordered sequence in order to accept or reject it. Since, e6 was not part of Tk, it means that { e1, e2, e3, e5, e6} form a cycle. Coming back to Tk1: e6 can’t be part of Tk1 since it forms a cycle with the previously picked edges {e1, e2, e3, e5}.

So, we have proved that if a Kruskal-produced MST and a random MST differ in an edge of the same weight, then we can apply Kruskal’s algorithm to rectify this difference.

Case 2: Let’s get back to the sample edge sequence (reproduced here for our convenience):

1 (e1), 2 (e2), 3 (e3), 4 (e4), 5 (e5), 5 (e6), 5 (e7), 6 (e8), 7 (e9), 8 (e10), 8 (e11), 8 (e12), 8 (e13), 9 (e14), 10 (e15), …. , (em).

Again, let Tk be a Kruskal-produced MST, and T be a random MST of G.

Let’s assume that T and Tk agree on edge selections until edge, e7. Also, let us assume that Tk does not contain e8, while T contains e8.

We can easily prove that this is not possible. The two facts that T agrees with Tk on edges e1 through e7, and that e8 is part of T, imply that e8 is compatible with Kruskal’s selection edges from e1 through e7. By definition, Kruskal’s algorithm must accept e8. Hence, the fact that e8 is not part of Tk is not possible. Hence, case 2 is an impossibility.

Case 3: Consider the same edge sequence:

1 (e1), 2 (e2), 3 (e3), 4 (e4), 5 (e5), 5 (e6), 5 (e7), 6 (e8), 7 (e9), 8 (e10), 8 (e11), 8 (e12), 8 (e13), 9 (e14), 10 (e15), …. , (em).

T and Tk notations are also inherited from above.

Assume that T and Tk agree on edge selections from e1 through e9. Also, assume that T contains two edges of weight, 8, say e10 and e11. On the other hand, assume that Tk contains only one edge of weight, 8, say e12.

To rectify the fact that Tk contains e12 but not e10, we apply the same arguments as in Case 1. Hence, we get that there can be a Kruskal-produced MST, call it TK1, that contains e10 but not e12.

Now, can e11 be made to be a part of a Kruskal-produced MST that contains e10 but not e12? The arguments here are similar in nature to those in Case 2. We can prove that such a case can not exist.

Case 4: Here’s the same sequence:

1 (e1), 2 (e2), 3 (e3), 4 (e4), 5 (e5), 5 (e6), 5 (e7), 6 (e8), 7 (e9), 8 (e10), 8 (e11), 8 (e12), 8 (e13), 9 (e14), 10 (e15), …. , (em).

Using the same meaning for T and Tk, we shall assume that T and Tk agree on edge selections from e1 through e8. Also, assume that Tk contains e9, while T does not contain e9.

Add edge, e9 to T. We get a cycle. It can be observed that this cycle will contain an edge with index greater than 9. i.e. one edge from among the set {e10, e11, …, em}. (This is  because, if e9 formed a cycle composed exclusively of edges selected by Kruskal from e1 through e8, it would not have been a part of Tk in the first place. Hence, the presence of a higher-indexed edge is essential in the cycle).

Now, we can remove the higher-indexed, and hence, higher-weighted edge, say  f, from the cycle and replace it in the MST, T by e9. This new tree, T – {f} + {e9}, is lower in weight than T. This is not possible. Hence, Case 5 is also an impossibility.

Case 5: Here’s the same edge sequence:

1 (e1), 2 (e2), 3 (e3), 4 (e4), 5 (e5), 5 (e6), 5 (e7), 6 (e8), 7 (e9), 8 (e10), 8 (e11), 8 (e12), 8 (e13), 9 (e14), 10 (e15), …. , (em).

Assume T and Tk agree on edge selections from e1 through e9. There can be a possibility that Tk contains 2 or more edges of weight 8, while T contains just one of them. We can show by arguments similar to those in Case  4 that such a possibility does not exist.

The cases that were considered were chosen so as to represent all possible types of interesting situations that might arise. There may be other cases possible, but hopefully it would reduce to one of these.

Explanation of this problem through an example makes, I believe, it easier for the reader and certainly, the writer. It is indeed a very long explanation, and probably one may want to think of the answer themselves.

So, Kruskal’s Algorithm does produce all possible MSTs of a graph G.

Some Practical Implications of this Result:

Whenever one is asked to prove that a given spanning tree is not an MST, we just need to show that the given tree can not be produced by Kruskal’s algorithm.

We had seen an interesting fact at the beginning of this post, that uniqueness of edge weights implies uniqueness of MST. (Note that we did not use this fact anywhere in showing that Kruskal’s algorithm produces all MSTs.) This is easily proven since Kruskal’s algorithm produces only one MST when run on a graph with unique edge weights, implying that only one MST exists for such a graph.

Jokes: Methods of proof

How to prove it

(from http://www.workjoke.com/mathematicians-jokes.html )

proof by example:

The author gives only the case n = 2 and suggests that it contains most of the ideas of the general proof.

proof by intimidation:

“Trivial.”

proof by vigorous handwaving:

Works well in a classroom or seminar setting.

proof by cumbersome notation:

Best done with access to at least four alphabets and special symbols.

proof by exhaustion:

An issue or two of a journal devoted to your proof is useful.

proof by omission:

“The reader may easily supply the details”
“The other 253 cases are analogous”
“…”

proof by obfuscation:

A long plotless sequence of true and/or meaningless syntactically related statements.

proof by wishful citation:

The author cites the negation, converse, or generalization of a theorem from the literature to support his claims.

proof by funding:

How could three different government agencies be wrong?

proof by eminent authority:

“I saw Karp in the elevator and he said it was probably NP-complete.”

proof by personal communication:

“Eight-dimensional colored cycle stripping is NP-complete [Karp, personal communication].”

proof by reduction to the wrong problem:

“To see that infinite-dimensional colored cycle stripping is decidable, we reduce it to the halting problem.”

proof by reference to inaccessible literature:

The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Slovenian Philological Society, 1883.

proof by importance:

A large body of useful consequences all follow from the proposition in question.

proof by accumulated evidence:

Long and diligent search has not revealed a counterexample.

Funny Math

Well here are some maths jokes. These are taken from http://www.math.utah.edu/~cherk/mathjokes.html and from http://www.math.ualberta.ca/~runde/jokes.html. These sites have got many more of these.

An infinite crowd of mathematicians enters a bar.
The first one orders a pint, the second one a half pint, the third one a quarter pint…
“I understand”, says the bartender – and pours two pints.

———————————————————————————————————-

Q: When did Bourbaki stop writing books?
A: When they realized that Serge Lang was a single person…

———————————————————————————————————-

Classification of mathematical problems as linear and nonlinear is like classification of the Universe as bananas and non-bananas.

———————————————————————————————————-

A tragedy of mathematics is a beautiful conjecture ruined by an ugly fact.

———————————————————————————————————-

The difference between an introvert and extrovert mathematician is: An introvert mathematician looks at his shoes while talking to you. An extrovert mathematician looks at your shoes.

———————————————————————————————————-

An engineer, a physicist and a mathematician are staying in a hotel.
The engineer wakes up and smells smoke. He goes out into the hallway and sees a fire, so he fills a trash can from his room with water and douses the fire. He goes back to bed.

Later, the physicist wakes up and smells smoke. He opens his door and sees a fire in the hallway. He walks down the hall to a fire hose and after calculating the flame velocity, distance, water pressure, trajectory, etc. extinguishes the fire with the minimum amount of water and energy needed.

Later, the mathematician wakes up and smells smoke. He goes to the hall, sees the fire and then the fire hose. He thinks for a moment and then exclaims, “Ah, a solution exists!” and then goes back to bed.

———————————————————————————————————-

A math student is pestered by a classmate who wants to copy his homework assignment. The student hesitates, not only because he thinks it’s wrong, but also because he doesn’t want to be sanctioned for aiding and abetting.
His classmate calms him down: “Nobody will be able to trace my homework to you: I’ll be changing the names of all the constants and variables: a to b, x to y, and so on.”
Not quite convinced, but eager to be left alone, the student hands his completed assignment to the classmate for copying.
After the deadline, the student asks: “Did you really change the names of all the variables?”
“Sure!” the classmate replies. “When you called a function f, I called it g; when you called a variable x, I renamed it to y; and when you were writing about the log of x+1, I called it the timber of x+1…”

———————————————————————————————————-

Q: How does one insult a mathematician?
A: You say: “Your brain is smaller than any >0!”

———————————————————————————————————-

There are 10 kinds of mathematicians. Those who can think binarily and those who can’t…

———————————————————————————————————-

Q: What is the difference between a Ph.D. in mathematics and a large pizza?
A: A large pizza can feed a family of four…

———————————————————————————————————-

A chemist, a physicist, and a mathematician are stranded on an island when a can of food rolls ashore. The chemist and the physicist comes up with many ingenious ways to open the can. Then suddenly the mathematician gets a bright idea: “Assume we have a can opener …”

———————————————————————————————————-

The physicist and the engineer are in a hot-air balloon. Soon, they find themselves lost in a canyon somewhere. They yell out for help: “Helllloooooo! Where are we?”
15 minutes later, they hear an echoing voice: “Helllloooooo! You’re in a hot-air balloon!!”
The physicist says, “That must have been a mathematician.”
The engineer asks, “Why do you say that?”
The physicist replied: “The answer was absolutely correct, and it was utterly useless.”

Note on the Formula for PI

In the previous post, we saw that PI = Lim (theta->0) 360 *  sin(theta/2) / theta. (Here, theta is in degrees.)

Now, we all know that standard result: : Lim (x -> 0) sin x / x = 1.  (Of course, x is in radians here.)

Important note: We’ll use Boldface for values in radians, and normal for degrees.

At first glance it may seem that Lim (theta->0) 360 *  sin(theta/2) / theta = 1/2 * 360 = 180, and not PI.

So how can we verify that our formula for PI is actually correct?

The reason is rather simple. It is because: Lim (x->0) sin x / sin x = PI / 180. ( Numerator: x in degree; Denominator: x in radians).

Proof:

Lim (theta->0)  sin theta/ sin theta ( Numerator: theta in degree; Denominator: theta in radians).

=  Lim (theta->0)   sin ( PI * theta / 180) / sin theta.    [ Now both numerator and  denominator have value of the angle in radians.]

= Lim (theta->0)   [sin (PI * theta / 180) / (PI * theta / 180)]   *  [ (PI * theta / 180) / sin theta]

Now, Lim (theta->0) [sin (PI * theta / 180) / (PI * theta / 180)] = 1  ( We can use the standard limit formula here since the angle is in radians.)

and,  Lim (theta->0) [ (PI * theta / 180) / sin theta] =  PI / 180.  (Again we can use the formula since angle is in radians.)

therefore,  Lim (theta->0) sin theta / sin theta = PI / 180.

Using this, the formula for PI in the previous post can be verified.

Formula for PI

The ancient mathematicians calculated the value of PI to a number of significant digits.  Everyone knows the definition  of PI: ratio of circumference of a circle to it’s diameter.

Now, how did the value 3.1415… come? How might have the first person calculated the numerical value of PI?

Key idea: We need a good approximation to the value of circumference. How do we do that? Take an infinitesimally small arc and approximate its length to that of the corresponding chord.

Consider an arc (AC) of the circle describing angle : theta (in degrees) at the centre of the circle (B)

.    A
.      /
r   /
. /   Angle B=theta
/——————-
B             r       C

Here, r is the radius.

We can complete the triangle by joining AC.

Now length of side AC =   sin(theta) * [ r / sin[(180-theta)/2] ] (Using the sine formula on triangle ABC, and since  angle A = angle C = (180 – theta) / 2])

Now we can use simple results to get :    length of side AC = 2 * r * sin(theta/2).

( since  : sin [(180 - theta)/2] = sin (90 – theta/2) = cos (theta/2)   &  sin(theta) = 2 sin(theta/2) cos(theta/2). )

Key idea (once again): As (theta->0),  length of side AC -> length of arc AC;
and circumference of circle = length of arc AC * (360/theta)

Hence, ratio of circumference to diameter = PI=  Lim (theta ->0) (360/ theta) * (length of arc AC) / (2 * r)

= Lim (theta ->0) (360/theta) * [2 * r * sin(theta/2)]  / [2*r]

= Lim (theta->0) 360 *  sin(theta/2) / theta.

So, there we have it: PI = Lim (theta->0) 360 *  sin(theta/2) / theta.

We can check using a calculator:

For theta =  1:    PI = 360 * sin(0.5) / 1.0  = 3.14155

For theta = 0.002:   PI = 360 * sin(0.001) / 0.002 = 3.14159.

Number patterns

Number theory has amazing patterns. Well, here I’ll give some interesting ones on sums of digits.

Sum of digits (s.o.d) of a natural number is found simply by computing the number modulo 9. (eg. s.o.d 157= 4)

Consider powers of  2. The sums of digits of the powers follow an interesting cycle- 1, 2, 4, 8, 7, 5.

1*2 = 2

2*2=4

4*2=8

8*2=16=7 (mod 9)

16*2=32=5 (mod 9)

32*2=64=1 (mod 9)

And again the same cycle repeats after 64. (s.o.d 128 = 2; s.o.d 256 = 4, and so on.)

Well, intuitively the proof is simple.

It follows from the result that s.o.d ( product of 2 numbers) = s.o.d of 1st number * s.o.d of 2nd number.

i.e. if we have 2 natural numbers, x and y; then s.o.d (x*y) = s.o.d (x) * s.o.d (y).

The result on product of s.o.d of numbers can be broken down further; that is, the above result can be obtained from the fact that s.o.d ( sum of 2 numbers) = s.o.d of 1st number + s.o.d of 2nd number.

From the result on product of sums of digits, the pattern stated above for powers of 2 is easily obtained by induction.

Well, we can state similar pattern for different numbers:

The cycle for the powers of 5 is 1, 5, 7, 8, 4, 2.

Now, we can see an interesting design- the cycle for powers of 5 is “opposite in direction” to the cycle for powers of 2.

Well, this is actually to be expected, and one can easily see intuitively why this is so. I leave it for the reader to figure it out. (Hint: 2^n * 5^n = 10^n = 1 (mod 9) ).

So the cycles for 2 and 5 are of lengths 6 each. The cycle length for powers of 7 is 3 (Cycle is  {1, 7, 4}.)

The cycle for 11 is 1, 2, 4, 8, 7, 5. Hey, this is the same as that for 2. Why? 11= 2 (mod 9). That’s why. If 2 numbers are equal modulo 9, they will have the same cycle, right.