## Discrete Math 101: Fun with Combinatorics – 2

3. ${n \choose k} = {{n-1} \choose {k-1}) + {{n-1} \choose k}}$

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 $k-1$ players from among $n-1$ players.

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

Hence we have the above result.

———

4. ${n \choose k} = {{n-1} \choose {k-1}} + {{n-2} \choose {k-1}} + { {n-3} \choose {k-1}} + \ldots.$

Again our task is to select a team of k players from among n players – $P_1, \ldots, P_n$.

If $P_1$ is part of the team: We can select such a team in ${{n-1} \choose {k-1}}$ ways.

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

If $P_1$ and $P_2$ are not in the team, and $P_3$ 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. ${n \choose k} = \frac {n}{k} {{n-1} \choose {k-1}}$

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

Say we select $P_1$ 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 $k-1$ players from among $n-1$ players.

Now, let’s go back a step. What if we select $P_2$ to be the 1st player of the team, and select the remaining players for the team in ${{n-1} \choose {k-1}}$ 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 $n \times {{n-1} \choose {k-1}}$.

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

$n \choose k$ 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 $14 \choose 11$ 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 $14 \choose 11$ possible teams and pick one from among them.)

We can easily derive some interesting results using the above meaning of $n \choose k$.

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

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. $n \choose k$ = $\frac { n! } {k! (n-k)! }$

Look at it this way. We have n players, say $P_1, \ldots, P_n$, 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 $n \times (n-1) \times (n-2) \times \ldots \times (n-k)$ 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 $k!$ ways.

Therefore, we have: ${n \choose k} = \frac {n \times \ldots \times (n-k)} {k!} = \frac {n!} {k! (n-k)!}$.

——-

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.

## Heads I win, Tails you lose.

For the past few days, I’ve been reading the lovely book, The Art of Strategy, that I wrote a couple of years back, when I was in college. Okay, I was bluffing. Avinash Dixit and Barry Nalebuff wrote it. And, in case you were really credulous enough (euphemism for dumb?) to think that I indeed authored a book in my undergrad, then this book is probably just for you. You would probably need all the strategic thinking practice that the authors give you. Steven Levitt, coauthor of the celebrated Freakonomics, said about this book: “I liked it so much, I read it twice.” 🙂

Very few books are educative and fun at the same time. This one is! The authors take us on a thrilling ride exposing the fascinating facets of game theory.

Okay, let’s play a game that the authors designed for us. Whenever we need a impartial referee to resolve any disputes, we shall bring in the irrepressible George W. Bush. You see, if the referee is a strategic thinker himself, he might take sides….

So we are in a big open grass field. George W. Bush has planted 20 flags in the field. Mr. Bush was also kind enough to tell us the rules. You go first and remove either 1, 2 or 3 flags. Then I’ll go and remove 1, 2 or 3 flags. Then it’s your turn again to remove flags, followed by my turn, and so on. You win if I remove the last flag. I win if you remove the last flag.

(Wait a sec. Mr. Bush has something to say. “Both of you have to remove at least one flag whenever it’s your turn. You can’t say that you don’t want to remove any flag.” …. Nice rule that one.. If there was only one flag left, and it were my turn, my devious plan was to run away. That way, you wouldn’t have won. Mr. Bush…prescient?? Wow!)

Bush: Gentlemen, let the play begin!  (To evade accusations of gender bias, I promise that if I ever post on game theory again, you will be assumed to be a girl. )

You remove 3 flags.

Ok.. 17 left…

I remove 1 flag.

16 left…

You remove 2.

14 left ….

I remove 1.

13 left…

(Ah… there’s a “I know something that you don’t” sort of grin on my face now. 🙂

You ignore my facial expressions and remove 2 flags.

11 left …

I remove 2.

9 left …

You remove 1.

8 left …

I remove 3.

5 left …

Oh wait. You suddenly seem to become dispirited. Come on, it’s just a game!

Putting on a brave face, you remove 2 flags.

3 left …

I remove 2.

1 left …

🙂

Let’s assume there were only 2 flags (instead of 20). Also, let us assume I take first turn. Okay, so I remove one. You’re doomed.

Now, let’s assume we had 3 flags planted in the ground. Again, me first. I remove 2 flags. You are left with the last flag. You’re again doomed.

Okay, now let’s assume there are 4 flags on the ground. My turn again. I remove 3. Sorry. 🙂

So, we notice one thing here. If it is my turn, and there are either 2 or 3 or 4 flags on the ground, I can always play cleverly and ensure that I win.

Now, let’s assume there are 5 flags on the ground. And it is my turn. If I remove 1 flag, you are left with 4 flags on the ground on your turn. Therefore, you can apply what we saw above, and ensure that you win.

So, if I remove 1 flag, you can ensure that I lose.

What if I remove 2 flags? You are left with 3 flags on your turn. Again, if you are clever, you can ensure that you win.

Now, what if I remove 3 flags? This time you’re left with 2 flags. And once again, you can ensure that I lose.

So what do we observe here? If there are 5 flags on the ground and it my turn, then I am doomed (assuming you are smart).

To summarize what we saw so far … (Let the two players be Player A and Player B.)

– If it is Player A’s turn and there are 2, 3  or 4 flags on the ground, then he can always ensure that he wins. (In other words, Player A has a “winning strategy” [ a strategy using which Player A will win irrespective of what Player B does]. )

– If it is Player A’s turn and there are 5 flags on the ground, then whatever Player A does, he can not win (assuming, of course, that Player B is clever).

Returning to our game, my strategy will be to ensure that when it is your turn you are left with 5 flags. And, also that, by no chance, should I leave you with 2, 3 or 4 flags on your turn.

Okay, now let’s suppose there are 6 flags on the ground, and it is my turn. What do I do? I remove 1 flag. That leaves you with 5 flags, which, as we just saw, places you comfortably on the “highway to hell” (I just wanted to include that phrase; I know it doesn’t quite fit in here. Ah who cares. 🙂

So by removing 1 flag from 6 flags when it is my turn, I can ensure that I win. That is, just to re-emphasize (at the cost of repetition), my winning strategy when I am left with 6 flags, is to remove 1 flag.

What if I have 7 flags left on my turn? I remove 2 flags, of course. This ensures that I will win eventually (i.e. winning strategy).

8 flags, my turn? I remove 3 flags; placing me comfortably on the “stairway to heaven”. (Again, just wanted to use the phrase. )

9 flags, my turn? I am doomed. Whatever I do, you can ensure that I lose.

Thus, if Player A and Player B are in this game, Player A’s strategy will be to leave Player B with 1 or 5 or 9 flags. Player B will have a corresponding strategy with just the roles reversed.

You see the pattern? If I leave you with 13 flags, you will necessarily lose. Similarly, if you leave me with 17 flags, you can make sure that I lose.

So, when you started the game with 20 flags, had you removed 3 flags, and played sensibly thereafter, you would have ensured that you win.

This is just one of the numerous interesting games described in Dixit and Nalebuff’s book (and a very simple one at that).

Unable to find a fine ending to this post, I think I’ll just copy what Dixit and Nalebuff wrote at the end of the Introduction:

“We warn you that some of the strategies that are good for achieving these goals may not earn you the love of your rivals. If you want to be fair, tell them about our book.”

🙂

## 12 days of Christmas

This is such a sweet song.

There are other versions of this song on YouTube.

This is a funny Indian version of the song.

## Conspiracy Country; Sceptic Society; Irrational Ideology

Welcome to the Islamic Republic of Pakistan.

“The state of Pakistan occupies an area which was home to some of the earliest Neanderthal settlements, some of whose descendants can still be found hiding in caves in the mountains of North Pakistan. The only difference is, in the Stone Ages, these Neanderthals were armed with clubs and stones, and today they are armed with guns and bombs. Remarkably though, they remain as furry as they were millions of years ago.”  (from Nadeem F. Paracha’s profile of Pakistan from the Pakistani newspaper, Dawn.)

Among the major pastimes of this truly one-of-a-kind nation are a passion for brainwashing already dim-witted persons till they can proudly reach the level of absolute and unabashed cretins, equipping such remarkable young men with bombs, and sending them wherever they can be sent to. With the explosion of private news channels and free media in this (literally) “land of the pure”, the subnormal intelligence and stunted intellectual growth of some of its citizens, hitherto unknown to the outside world, has come to the fore as never before. The electronic media has proved itself to be the incontrovertible leader in producing astoundingly dumb conspiracy theories. It would seem to a sane observer than institutional paranoia and a stubborn refusal to use any mental faculty characterizes this peculiar society, as evidenced in certain excellent specimen like Zaid Hamid and Ahmed Quraishi. Thus, while the export of terrorism has continued unabated, Pakistan now also continually exports top-class humour through such enlightened individuals.

Here are some articles on conspiracy theories doing the rounds in Pakistani news channels.

A New York Times article – US is a top villain in Pakistan conspiracy talk.

A Reuters blog post on some of these theories – Pakistan’s conspiracy theories.

A post from The Lede blog of New York Times – A grand conspiracy theory from Pakistan.

Another post from The Lede blog –  Taliban blames Blackwater for Pakistan bombings.

An article from the Dawn newspaper-  The convenient curtain of myth

A BBC article on the subject –  Pakistan conspiracy theories stifle debate.

## Sanskrit lesson – simple verbs 2

Some more simple verbs.

१. पा (to drink); e.g. मृग: पिबति। (The deer drinks.)

२. सृ (to go); e.g. बालक: सरति। (The boy goes.)

३. क्रीड् (to play); e.g. बाल: क्रीडति। (The little boy plays.)

४. खाद् (to eat); e.g. सिंह: खादति। (The lion eats.)

५. दृश् (to see); e.g. शिक्षक: पश्यति। (The teacher sees.)

६. गर्ज्् (to roar) e.g. मेघ: गर्जति। (The cloud emits a thundering sound.)

७. कृ (to do); e.g. छात्र: कार्यं करोति। (The student does work.)

८. कूर्द्‌ (to jump); e.g. वानर: कूर्दति। (The monkey jumps.)

९. द्रु (to run); e.g. अज: द्रवति। (The goat runs.)

That’s all for now.