At The End Of The Rainbow

I am one of the few people who loves rain. One reason is the rainbow, whose scientific explanation has not dulled it's beauty to me. This one was very near my home. These shots are from my window.

The Assassination of Jesse James by the Coward Robert Ford

Movie Review : The Assassination of Jesse James by the Coward Robert Ford
Director : Andrew Dominik
Genre : Western
Released : September 2007
Starring : Brad Pitt, Casey Affleck
My Rating : 4 out of 10

I decided to watch this movie based on the curious title, the cast and the true story on which it is based. Sadly, this turned out to be a long movie (with a long title) - a whole 160 minutes -  that feels way longer than even that. I thought I was watching it for like 5 hours.

First the good news. Great acting by Casey Affleck. Really superb. Very nice cinematography. Last 30 minutes are well scripted. That's about it.

Bad news is plenty. Brad Pitt is not a bad actor, but he is badly cast as Jesse James. Completely unbelievable portrayal. A large number of unnecessary scenes. And they are slower than snail. You will learn almost nothing about Jesse James. There is zero tension in scenes that should have been tense. It's hard to care either way about any character except Robert Ford (Casey Affleck).

And the movie takes itself way too seriously. It's absurdly pretentious.

There really isn't much of a synopsis to write about.

I don't mind watching long slow movies at all. But there has to be enough return on investing so much time. Not here.

Had this movie been cut down by half to 80 minutes, I might have a given a tentative recommendation based on the camera work and Casey Affleck's acting. As it stands, you are better off not watching this one.

Humpy Koneru

I know Cricket World Cup is happening, but this is an important news, that should not be overshadowed. India's highest rated woman GM, Humpy Koneru, has qualified as a challenger to play for the title of the Woman's World Chess Champion against the current World Champion - Chinese GM Hou Yifan !

Humpy has been a leading female player for a while. With some impressive results so far (like winning Girls Junior world championship title). She has been awarded Arjuna Award and Padma Shri by the Indian Government.

The current Woman's World Champion Hou Yifan is a phenomenally talented 17 year old. She won the title when she was 16 years old - and created the record of being the youngest person in the history to win a chess world championship.

Apart from the highest rated female player Judit Polgar (who does not participate in Woman only tournaments), these are the only 2 other girls rated over 2600. So they are the logical contenders for the championship. But the match would be tough for Humpy - in their games so far, Hou has won 7, and Humpy only 2.

If Humpy wins the match later this year, both male and female World Chess Champions would be Indians.

Partial Derangement

As part of a bigger problem, I wanted to solve what I decided to call "Partial Derangement". This may be part of standard course material on Combinatorics, but I couldn't quickly find anything similar. So I gave it a try on my own. I may be reinventing a wheel here, but it was a fun challenge.

The problem is similar in nature to "derangement". In the derangement problem, we want to find out all such arrangements, which do not have any object in its correct place. Here the restriction is placed on only a few items. Say you want to find out arrangements of letters [A B X Y] such that A cannot be in first place, and B cannot be in second place. There is no restriction on X and Y .

For example, [B X Y A] is a valid arrangement. But [X B A Y] is not. Because here B is in its natural second place.

Let's modify the problem we looked at, while discussing "derangement".

Say M men and W women went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, all the men deliberately put on a wrong name tag on their shirts. No man had the right name tag. The women, on the other hand can put the right name tag if they want. In how many ways can they do it ?

Note how this is quite different from simple derangement discussed before. Here a man can put a woman's name tag to satisfy the requirement of the game. For every man, there are (M-1) * W valid choices. Whereas in a simple derangement, every man would have had only M-1 choices. In other words, this is NOT a derangement only within a subset. Hence the answer cannot be D(M) * W! where D(M) is number of derangements of a set of M objects.

This problem is a bit harder than derangement. But very similar logic can be applied to solve it. First, let's define what we want to solve for.

Let's define, PD (N, K) as the number of arrangements of N items, out of which particular K predefined objects cannot be in their correct place. Note that there are specific K objects, already identified to be deranged.

Think of N numbered balls (from 1..K..N) to be put in N numbered bins (from 1..K..N) . The task is to arrange N balls so that no ball numbered (1..K) is in the bin with the same number.

We will solve it using the similar reasoning style for derangement.

Pick a ball, numbered between (1..K) This ball i can either

A : Be put in any unrestricted bin, which is numbered (K+1..N) In this case, any bin can be used, there is no restriction. There are N-K choices for such a bin.

OR

B : Be put in a restricted bin from (1..K) There are K-1 choices here, as ball i cannot be put in bin i .

Let's examine each case in more detail now.

A : When the ball i is put in an unrestricted bin, we lose one unrestricted bin, of course. But now the corresponding bin i for this ball becomes unrestricted, as any ball can be put there without violating the rule. Meaning the number of unrestricted bins remains same, and the number of restricted bins is now one less. So after this placement, we have N-1 balls, with K-1 restricted bins. This is same as PD(N-1, K-1) . And since there are N-K choices for choosing an unrestricted bin, the sub-total of these arrangements is (N-K) * PD(N-1, K-1) .

B : This is where I am copying the logic used in finding derangement. Here ball i was placed in a restricted bin, from (1..K) . Since it cannot be placed in its own bin, there are K-1 choices for this. Let's say it was placed in bin j . Now let's decide a place for the ball j corresponding to that bin. There are 2 choices - it is either placed in bin i or it isn't.

B1 : It is placed in bin i . This effectively removes the pair i and j from the set. We are left with N-2 balls, to be placed in N-2 bins, out of which K-2 are restricted bins. This is same as PD(N-2, K-2) .

B2 : If ball j is not be placed in bin i, let's represent that restriction by simply renaming bin i to bin j. This leaves us with exactly the same problem, with one less ball. That is, we have N-1 balls, with K-1 restricted bins. This is nothing but PD(N-1, K-1) .

Since B1 and B2 are mutually exclusive, for every choice of bin for ball i we have 

PD(N-2, K-2) + PD(N-1, K-1) 

arrangements. Since there are K-1 choices for bins, the subtotal here is 

(K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) ) .

Since, A and B are mutually exclusive, let's add them to get the final answer.

PD(N, K)
= (N-K) * PD(N-1, K-1)
+ (K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) )
Note the term PD(N-1, K-1)is common in both. So after simplifying, we get a nice elegant formula
PD(N, K) = (N-1) * PD(N-1, K-1) + (K-1) * PD(N-2, K-2)

To use this formula, we have to have certain definitions, to avoid negative values. This is similar to saying 0! = 1 by definition, to terminate the recursion of formula  N! = N * (N-1)!

PD(0, 0) = 1 (by definition)
PD(N, 0) = N! (No restricted bins, so all arrangements are valid)

We require one last definition, and it needs some explanation.

PD(N, 1) = (N-1) * (N-1)!

Here we want to know how many arrangements are there, in which one specific ball is not in its corresponding bin. The total arrangements are of course N!. How many invalid arrangements are there ? To find out put the ball in its corresponding bin and arrange the rest of the N-1 balls. This is nothing but (N-1)!. So we have

PD(N, 1)
= N! - (N-1)!
= N*(N-1)! - (N-1)!
= (N-1) * (N-1)!

Let's do a couple of quick checks.

PD(1, 1) = (1-1) * 0! = 0
Obviously, there is no way to arrange just 1 ball with our restriction.
And
PD(2, 1) = (2-1) * 1! = 1
Correct, as there is only 1 way to arrange 2 balls with out restriction.

Let's also check if we are in agreement with full derangement.

PD(N, N) is full derangement - no ball in its corresponding bin, so this should be equal to D(N) .

Let's see. Using our formula,

PD(N, N) = (N-1) * PD(N-1, N-1) + (N-1) * PD(N-2, N-2)
= (N-1) * ( PD(N-1, N-1) + PD(N-2, N-2) )
= (N-1) * ( D(N-1) + D(N-2) ) (using induction)
= D(N)

This was definitely harder than derangement, but it was also much more fun to prove a more general result.

Anoop Desai

Anoop Desai was a contestant in American Idol season 8, finished at 6th place. His first music video is out. Pretty good song for a newbie.