Casablanca

Have you seen Casablanca ?

Classic Hollywood 1942 movie starring Humphrey Bogart and Ingrid Bergman. Definitely on any top 10 movie site. Simple plot, great actors, nice ending. Often been borrowed from, and its dialogues been referred to for decades after.

Bogart and Ingrid have a fabulous and rare chemistry, and Bogart's cold, cynical character has awesome witty dialogues - you can read nearly half the movie if you go to IMDB Memorable Quotes. Who hasn't heard the now-a-classic line "Play it Sam. Play As Time Goes By" ? And who can forget "Of all the gin joints ..." ?

Even the minor characters, played by actors like Peter Lorre and, especially, Claude Reins, are superb. ( "I think this is the beginning of a beautiful friendship ..." )

Well, all that is very well, but those are not the reasons I'm writing about Casablanca. My reason is Ingrid Bergman.

I swear, Ingrid in Casablanca is the most gorgeous woman I've ever seen on television.

Ingrid was a beautiful woman, no doubt, but in this movie she's just awesome. No other photograph, no other movie of her even comes close to her looks in this movie. And I don't mean that she wears a hot dress in this movie or anything like that; she just looks oh so beautiful. Every time I've seen the movie, every single time, just as soon as she entered the screen, I breathed "Wow!"

"Here's looking at you, kid !"


It's a good movie. If you haven't seen the movie, you might want to.
A Franc for your thoughts ?

p.s. It goes like
( Ilsa, to a pensive Rick: A Franc for your thoughts ?
Rick: In America they'd bring only a penny, and, huh, I guess that's about all they're worth.
Ilsa: Well, I'm willing to be overcharged. )

Arbit 2

In one of my internship interviews, I was asked a puzzle that I took over 10 minutes to answer:

"There are 100 prisoners about to be executed the next morning, in the following fashion - they are standed in a queue, and on every head a hat is placed, either white or black. (Number of white or black hats not known in advance). Now, starting from the last person, prisoner#100 to prisoner#1, each one says a colour of these two. (Every one can only see all the people in front but can hear what any person says.) Then only the prisoners who guessed their hat's colour correctly, survive. Rest die. They are told this the night before; come up with a strategy that saves as many of them as possible."

I started thinking with the easiest solution - even numbered person speaks the colour of the person in front, who repeats what they just heard. This way, 50 people definitely live, others have a 50-50 chance, so expected number of survivors is 75. But this was just the first thought, this can obviously be greatly improved.

( Solution follows this, so if you wanna think on your own first, do so before reading further. )

The solution I finally gave was that the prisoner#100 counts the white hats she can see, and says white if the number's even and black if it's odd. Prisoner#99 now counts the white hats she can see, and if her count is same (odd/even) as prisoner#100's count (odd/even), her hat must be black, otherwise white. So she says the colour of her hat. Prisoner#98 now counts the white hats (counts prisoner#99's hat too if it was white), compares this value with prisoner#100's count, and by same reasoning gets her colour. And so on to the first prisoner, who will only consider the colours of prisoners 99 to 2 when counting hats, and by same logic gets her colour.

So, the first 99 people definitely survive, and the last person has a 50-50 chance.

So far, so good. But later, after the interview, I started thinking, what if there were not 2 types of hats, but three - red, blue and green? Can the solution be modified to still save 99 people? What if there were n types of hats? Can 99 people be saved then? I found that a simple generalization serves the purpose.

( Again, if you want to think on your own, do so before reading further. )

Lets start with 3 colours of hats - Red, Blue and Green.
Prisoner#100 counts number of red hats (r) and the number of blue hats (b), and calculates m100 = (2*r + b) mod 3 . She then says R, B or G depending on whether m100 is 0, 1 or 2 respectively. Note that depending on this colour, everyone now knows m100. Prisoner#99 now counts hats and finds m99 = (2*r + b) mod 3. Now her colour is R, B or G if (m100-m99) mod 3 is 2, 1 or 0 respectively. Again, prisoner#98 counts hats, also considers prisoner#99's colour, then finds (m100-m98) mod 3, and by same reasoning finds her colour. And so on until the first person.

Just as before, first 99 prisoners live, and the last person has a 1 in 3 chance.

Similarly, for n colours - C1, C2... Cn. We just generalise this process.
Prisoner#100 counts numbers of hats of colour C1(r1), number of hats of colour C2(r2) and so on till Cn-1 (rn-1), and finds m100 = { (n-1)*r1+(n-2)*r2+... 1*rn-1 } mod n. She then says C1, C2... or Cn-1 if m100 is 0, 1, 2 .. or n-1 respectively. Prisoner#99 now counts hats and finds m99, and her colour is C1, C2... or Cn if (m100-m99) mod n is n-1, n-2 ... or 1 respectively. Again, prisoner#98 counts hats, also considers prisoner#99's colour, then finds (m100-m98) mod n, and by same reasoning finds her colour. And so on until the first person.

Once again, first 99 prisoners live, and the last person has a 1 in n chance.

The most interesting aspect of this generalization comes when the number of colours, n, tends to infinite. Just imagine the odds against the 100 men - they all have to guess the colour of their hats when the number of options to choose from is unimaginably huge. Despite the odds, their strategy lets the first 99 prisoners live. But the last person has a 1 in n chance of survival!

So, here's the funny part - infinite colours, yet 99 prisoners guess correctly thanks to the last person, who certainly dies. Funny, huh?

Arbit

For my first log, I'll tell ya about something arbitrary that I find cool.

As a child, you must've known the age-old children's puzzle - Draw the following without lifting pen from paper and without repeating any line.
The age old solution is - you fold the paper and use the backside as a bridge to get from one point to another. It's a very general trick, and can be used to draw anything without lifting pen from paper.

Let's look deeper. Using graph theory, it's easy to show that the above figure has no path that uses each edge exactly once. (Just read euler paths on wiki.) The basic idea is that if there's such a path, every time it visits a vertex, it must leave the vertex using a different edge, and so the degree of every vertex must be even, except for the starting and ending vertex (if they are not same), in which case, they both must have odd degrees. In the above figure, the four ends of the square all have odd degrees, which makes it impossible for such a path to exist.

Actually, the above condition on degrees can be shown to be both necessary and sufficient for an Euler path to exist. So, consider the following figure:
(Same as figure 1, except each line is drawn twice.) Clearly, every vertex has even degree, as I just doubled the degree of every vertex. So, this figure has an Euler cycle.

This gives us a new solution to the age-old problem of drawing figure 1. You draw figure 2 instead, and then use the axiom - "What I can do twice, I can do once" ! Neat huh? My new solution too is a general trick; it can be used to draw anything connected. Ta-da!