The fascination that lasts

Farewell, Mr Gardner

2010-06-03T04:36:00.000-07:00

Martin Gardner, the first Mathemagician, the first editor of the column called Mathematical games in Scientific American and an author of over 70 thought provoking books on topics mostly related to mathematics, physics, logic and philosophy passed away on May 22 this year.

Given that he was 95, it had to happen sooner or later, but still his passing away came as a blow to me. I am a huge admirer of books by Gardner. I love trying out new puzzles and to me Gardner's books were God sent at a time when all I could see around myself were books by George Summers, Shakuntla Devi and Ravi Narula. I did not find these books to be any good as most of the puzzles they contained were not good enough. I could solve most of the problems of these books when I tried them and most of the time I did not feel like trying them as they were too boring -- to me, they looked like problems of grocery bill variety. I was of belief that good puzzles ought to have some "sort of life". Essentially what I was looking for were questions of the type which required some Aha! moments as Mr. Gardner put it.

Then I ran across several of his books - Aha! Insight, Aha! Gotcha, Puzzles and Diversions, Knotted Doughnuts, Penrose Tiles to Trapdoor Ciphers, Colossal book of Mathematics and a few other books. These books made mathematics look like sport. I am not saying they made mathematics look easy -- they made mathematics look fun. I also joined the group of people whose lives were affected by Gardner. As Conway, Berkelamp and Guy put it in their Winning Ways for your Mathematical Plays, Gardner truly brought more math to millions than did anyone else.

If you have heard of some good puzzle that you think requires some Aha! moment, chances are that Martin Gardner first popularized the puzzle in some of his columns or through some of his books.

His passing away certainly shocked me. But Martin Gardner has left an undying legacy behind him. You should definitely go and see his books if you have not seen them so far. I promise, it will be an Aha! experience.

I Salute you Mr. Gardner. Farewell, Sir.

Analyzing Riffle Shuffles

2010-02-02T14:36:00.000-08:00

Hello Everybody,

I am writing this narrative describing properties of riffle shuffle that we analysed in Markov Chains class recently. Its in three parts. The parts are identified by the ******* marks. If you want to skip to the technical material, read the last part - the one that follows the last star marks.

"No, no, no, its not possible", I checked the board again for the fourth (or fifth) time. But there it was. Sitting on the board it was a masterpiece of reasoning which produced that result.

I was still in the strong defiance stage. The three stages of digesting (rather assimilating) a hard to believe truth, that someone in some corner of the world sometime pointed out, huddled through my mind

Strong Defiance, Mild Reluctance....finally Admittance.

The result was so awe-inspiring that I immediately decided - I was going to blog about it. I told Prof Randall that I was about to blog on the topic. She gave a Dumbledoric smile. But I knew I had undertaken some responsibility. I started searching my mind for the way the lecture began. "No, this is not where I want to start", I told myself. After some pondering over the issue, I knew where to start now. Enjoy the rest of the post

**********************************************************************************

It started rather innocuously. Prof Randall was teaching something about hypercubes - and I drifted. I suddenly recalled a movie called hypercube and my attention was partly swayed. When I came back to myself, I had skipped a few sentences. "Damn, not again", I cursed myself. I cannot understand why this word hypercube triggers an imagery of sci-fi movies through my brain even in lectures.

But it was okay. I was able to follow the other parts of the lecture including the hypercube part itself. A few moments later, a doubt grabbed me. I wanted to get it clarified and lo - I forgot my doubt. This has happened to me before as well. But today was a different day. Two hated things happened on the same day in the same lecture. The irony is that I cannot even call it ironic as it was too moronic.

As it were, I was there sitting partly distracted by the latest turn of events, when a voice (a question that Prateek Bhakta asked) from behind brought me to my senses and made me attend the rest of the lecture that finished with a wonderful demonstration of some curious properties of riffle shuffles that I intend to discuss in today's post. This is the heart of today's post and forms the last part.

**********************************************************************************

So, what in Merlin's name is a Riffle Shuffle? Well it is a way to shuffle a deck of cards which we will shortly see randomizes the order of the cards in the deck in very quickly. Our analysis here uses some part of the lecture but also draws heavily from many other sources which I will mention towards the end of this post.

Let us begin the tour with a fairly simple question. You have got a deck of cards labelled $1,2...n$ from top to bottom on a table. Let us call this initial ordering of cards the identity permutation.

When can you claim that your shuffles have randomized the order of the cards in the deck? When indeed?

Put simply, this question asks "how many shuffles suffice?"

At a certain level you might feel like this question asks you to define randomness for which we do not have a very comfortable mathematical notion. But still, in some sense, we can answer this question. We rely on what we call total variation distance to save the day.

Informally, the idea is to estimate the "distance" of two probability distributions over all the possible permutations of cards in the deck.
Total variation between two probability distributions $P$ and $Q$ is given by $||P - Q|| = \frac{1}{2} \cdot \sum_{\pi \in S_n} \vert P(\pi) - Q(\pi) \vert$ where $\pi$ is one permutation and $S_n$ is the group of all possible permutations.
You pick one of these distributions as the uniform distribution and the other one as the distribution you generate after $k$ shuffles of your scheme. You hope to develop a scheme for which $k$ is not inordinately large (of course quantities of the order of $52!$ are an abomination, but so are quantities like $200,\ 100$ or even $50$ shuffles).

Hmmmm....what should we do. What indeed? The first idea might be to invoke what we call the coupon collector. The problem involves something like throwing a $n$-sided-dice and asks you to estimate the expected number of throws after which you can claim that all the faces have turned up atleast once. The answer can be given by summing up over a geometric random variable.

Here, in card shuffling, the idea can be to keep removing the top-card and inserting it someplace in the deck randomly. The stopping rule will be to say that you are done when you place the $n^{th}$ card someplace in the deck.

The idea for this is again intuitively obvious. There are two things that you will need a proof for. One - that it really achieves small total variation from the uniform distribution; two - it does so within the stated time bound.

That one holds can be understood this way - the order of cards below the original bottom card is really random. In expectation, when $i$ cards are already below the bottom card, it takes $\frac{n}{i+1}$ shuffles to get it in the desired position (i.e., anywhere below the bottom card). This explains the $n \cdot log(n)$ moves answer that you obtain if you do shuffling this way.

But you are not happy with this. With $n = 52$ cards, this works out to be more than $200$ shuffles. But we are not out of ideas yet. Not so fast. We will arrive at our target in less than 10 shuffles. Below we show how.

This technique is called Riffle Shuffle (henceforth RS). It involves cutting the deck of cards into two halves and then interleaving them in some fashion (so that you obtain a maximum of two interleaved increasing sequences) and keep repeating this process quite a few times. If you label the cards in the left hand all with a $0$ and those in the right all with a $1$, the two increasing sequences are those that are $0$-identified and those that are $1$-identified. This method really arrives at a distribution close to the uniform pretty fast.

Lets ask a simple question first. How many distinct RSs can you do on a deck of $n$ cards? It turns out, that if you have $t$ cards in one of your hands, number of possible RSs are $ n \choose t$ $-1$ (why?). Adding over all $t$'s, you get $2^n - n$ as the total number of possible RSs.

Lets also spare a look at the probability distribution on $S_n$ due to RS. It is fairly simple to explore and I would leave it to the reader to think why it comes out the way it does

$Rif(\pi) = \frac{n+1}{2^n}$ if $\pi$ is the identity permutation.
$Rif(\pi) = \frac{i}{2^n}$ if $\pi$ consists of two increasing sequences
$Rif(\pi) = 0$ otherwise

We are doing good. Now its time for the leap. "No, no, no, its not possible", I checked the board again.

Thing is, you can study what we call the inverse riffle shuffle (henceforth IRS) to analyze the number of number of riffle shuffles needed to randomize the deck. Both have the same mixing time! And that is amazing. Too amazing.

So, let me define IRS and tell you what its curious properties are which might help in understanding this beautiful concept. (The material below largely draws from the wonderful Proofs from the book by Martin Aigner)

An inverse shufle would take a subset of the cards in the deck, remove them from the deck, and place them on top of the remaining cards of the deck - while maintaining the relative order in both parts of the deck. Such a move is determined by the subset of the cards: Take all subsets with equal probability. Equivalently, assign a label $0$ or $1$ to each card, randomly and independently with probabilities $\frac{1}{2}$, and move the cards labelled $0$ to the top.

That IRS gives the same probability distribution as RS is obvious as you can check that you get the identity permutation precisely when all $0$-cards are above the $1$-cards.

So analyzing the IRSs is good enough! Also, as informally noted above, the inverse shuffles give a probability distribution $Rif(\bar{\pi})$ such that $Rif(\bar{\pi}) = Rif(\pi^{-1})$. Further, we know that Uniform permutation is pretty cool in that it allows $U(\pi) = U(\pi^{-1})$.

So, the following two quantites are same

$||Rif(\pi) - U|| = ||Rif(\bar{\pi}) - U||$.

Finally, we note when should we stop the iterations of IRS so that we can state with confidence that the deck is randomized. Let us suppose that you can do this after $k$ shufflings. Each shuffling, the IRS way, is according to the bit-that you assign to that card. SO, you can proceed by assuming that you assign a random $k$-bit string to the card. And then the cards fate is decided by the string it started out with. Two cards might still stay in same relative order if they started out with same bit strings. This can be avoided if all cards get distinct bit strings. So, the problem now reduces to a problem of Birthday Paradox. As I said, this was where I went through those stages

Strong Defiance, Mild Reluctance....finally Admittance.

I would invite you to show why. For the benefit of others, you can leave the proof as a comment.

Since, its 6'0 clock in the morning and I want to catch some rest, I will not do that now.

Have a Good Day
-Akash

Some fundamentals of Markov Chains

2010-02-02T14:07:00.000-08:00

Hello All,

This is a placeholder post. I will replace it with the contents that should be here soon.

Till then you might want to see the $7^{th}$ Chapter of Mitzenmacher-Upfal book

Some snapshots of Markov chains and Monte Carlo Methods

2010-01-11T16:41:00.000-08:00

Hello everybody,

Sorry for choosing such a bad name for today's blog. The problem is - this was the first lecture on the subject today, and I did not really know what else to call this blog.

Anyway, this semester, spring 2010, I am enrolled in a course called Markov Chains and Monte Carlo Method (henceforth MCMC) here at Georgia Tech. Our instructor is the wonderful professor Dana Randall and she has an amazing knack for surprising you in each of her lectures. I do not understand how she communicates her lectures this nice - which in essence is ,in my opinion, an art of explaining things effectively - an art I am really horrible at. I guess to explain this nice you have to understand nicer.

Anyways, enough belaboring, let me get to the point; but wait let me get some other things out of the way first.

(The section below definitely need some rework; I hope I will get around to do that)

The exposition in this series of lectures by Prof Randall will be mainly technique driven. That is, we will see the techniques that have evolved while we work with Markov Chains to solve some important problems in Graph Theory, Statistical Physics, Molecular Biology and other curious areas. We will begin our tour with some classical counting problems and see the power of Markov chains as they solve the problem for us by developing appropriate context and motivation.

Last but not the least, since I do not trust my memory fully, I may skip some of what Professor taught in the class owing to my RAM (memento style temporary memory, well not exactly memento style) and thus do a poor job of presenting the lecture's material (with high probability) and sometimes I may add a few extra things from my knowledge that could make the lecture's material a little easier to follow (with vanishingly small probability).

Now the lecture.

So, as I said above, we begin the tour with some classical counting problems.

So, let me just mention the following problem. Can you decide in polynomial time whether an arbitrary undirected graph has got a perfect matching or not? If you can, can you explicitly find that matching? Going further, can you count the number of matchings in an arbitrary undirected graph? Lastly, can you return an arbitrary perfect matching from the graph (assuming graph has got some finite number, $n$ of perfect matchings, this question asks you to select anyone uniformly).

If I tell you how to solve the $3^{rd}$ the first two problems become trivial. Also, if I tell you answer to the second one, first one becomes trivial. No sweat.

Thus, the first problem is no harder than the second one and the second one is no harder than the third one. What about the other way round?

It turns out if you have access to some oracle which can answer the first question (viz whether the graph has got a perfect matching or not) you can answer the $2^{nd}$ question as well. And given an oracle access to some device that solves the $3^{rd}$ question, you can answer the $4^{th}$ one. We will see in future posts how to do all these (if I get around to write some).

But let me remind you about the problem of counting perfect matchings in a bipartite graph. Its "cute" in the sense that it has a very good linear algebraic interpretation. Turns out, solving the above counting problem is as tough as computing the permanent of a matrix. You know permanent? Its just the determinants with all the "minuses" gone. And surprisingly its hard to compute permanent whereas computing the determinant (which involves some zig-zagging through 'signs") is easy. In fact, computing the permanent is #$P-Complete$.

Thus, given the above information you can see that counting the number of perfect matchings in an arbitrary general graph must also be, well, #$P-Complete$.

Now, lets see how the knowledge that a graph has a perfect matching helps in constructing one. Hmmm....So I tell you that I have a graph which has got a erfect matching. What good is this information in finding out one?

Pretty good it turns out. We capture the essence of the above discussion by saying that graphs are self reducible with respect to the perfect matching property. We will prove this later.

Now, I will turn to discuss something about a special bipartite graph, namely the chessboard. Turns out in a chessboard the number of perfect matchings is easily computable. First, lets turn to the following famous problem. You have a $n*n$ chessboard. Can you tile it up using $2*1$ dominos?

You can easily see that its not possible for odd n. For even $n$ its clearly possible. Too trivial. Now I ask is it always the case that you can tile up an arbitrary connected figure which has got an even number of squares. The answer is no. Consider the traditional chessboard with two opposite corners removed. Say the removed squares are both black. The number of white squares being more, domino-tiling is not possible anymore.

Thus, it looks like the sufficient condition for tilability is an elusive beast. Not if Prof Randall has her way. Somewhere, in the course of her graduate studies, she made the following cute observation.

Consider the following special "marked" dominoes (alongwith an unmarked one)

Call these figures (a), (b), (c) and (d). The marked tiles, (a), (b) and (c) respectievely connect $(x, y)$ to $(x+1, y-1), (x+1, y+1)$ and $(x+2, y)$.

Then Prof Randall makes a nice series of observations beginning with a very simple idea. She first says that if you can tile the board with unmarked dominoes only, then you can trivially put marks on them and obtain a marked tiling.

But a marked tiling is not she is happy with. She is looking for a meaningful marking - a marking which can tell her something about the number of perfect matchings in the above kind of graphs. In short, she establishes a bijection between the number of domino tilings and the number of perfect matchings. The mental gymnastics she went through for this are not very clear to me, but I can try imparting some intuition by "cooking up" the following explanation. Possibly, she arrived at this result by some other genius inventive idea; but the description below should help.

Note The discussion below uses the word domino and tiles interchangeably.

First, let us assume we are on a $n*n$ grid where $n$ is even. (We will discuss the general case for $\RR \subseteq Z^2$ later). Further, to assist our discussion imagine that squares are coloured black and white like they are in a chessboard. Also, think of your dominoes as all being transparent. Now, put a red dot over the center of the region of the domino which lies over a black square. Let us identify the starting point of a tile as this red dot lying over a black region on the tile.

You can now imagine the tiles as being some sort of "teleporter" carrying the red dot from one tile to the other. They can carry it "horizontally through" the tile as shown in (c), or "diagonally" as in (a) and (b).

[I am not providing any diagrams, but should you need one, you can look here on page 9.]

Thus, you obtain a triangular lattice whose edges correspond to the direction the "teleporter" carried the red dot in. If you can chalk out a simply connected path for red dot starting at some left boundary tile (source) and ending at some right boundary tile (sink), you basically just figured out a tiling for the squares you traversed on the original board.

Thus figuring a simply connected path on the triangular lattice corresponds to figuring out a tiling for the corresponding portion of the chessboard! Figure out a series of such non-intersecting paths, each beginning at some source $s_i$ and ending at some sink $t_i$ such that all the paths are non-intersecting; you win.

(If paths intersect, your tiles overlap - thats why we need them all to be disjoint). The series of paths from $s_i$'s to $t_i$'s is called routing. Thus, the number of domino-tilings of the chessboard is the same as the number of routings! Also, notice that a source-sink pair, $(s_i, t_i)$ is respected by all tilings. That is, if one arbitrary routing has got a set of sources $(s_1, s_2, ..., s_k)$ and a set of sinks $(t_1, t_2,...,t_k)$, all other routings will have the same set of source and sinks. Its easy to see why. If it were not, paths would intersect leading to pathologies (not to mention other disasters like earthquakes, vampires, stinking socks, filth, etc.)

You might have noticed that under the assumption that the region was tilable, the number of sources and sinks is the same. Figure out why on your own. (Its too trivial).

The same analysis extends to any other tilable $\RR \subseteq Z^2$.

But as of now we have not mentioned when is a region tilable. Relax, we are coming to it as well. We would do it using some tools from group theory. Our proof will be a constructive one, if there exist some tilings, it will find one.

Allow me to relax a bit. I will resume posting soon.

A further remark on the orb puzzle

2009-04-12T20:11:00.000-07:00

Here is a further remark on the orb puzzle also called the egg puzzle and (in)famously also called, because of interview forums, the 2 orb puzzle or the 2 egg puzzle.

Back here, in India, the object that guys have been using, since time immemorial, is an egg.

NOTE: In what follows, I would be using egg (and not orb) as the object of experiment. The title was chosen as "A further remark on the orb puzzle" as a homage to the mind of whoever first came up with this remarkable puzzle. Now you can gear yourself up for the further remarks, which to my best knowledge have not been accumulated elsewhere.

If you want to know what the puzzle and how to solve it, you can read my previous post.

Now that you have settled (assumption being you are aware of the puzzle and its solution) you can start reading what follows.

Somewhere, while doing the above question, my thoughts turned to a strange corner. I had solved the problem in its full generality and had also tried cases with different number of eggs and floors.

With 3 eggs, it took you 9 turns to cross 100 for the first time. With 4 eggs, this number was 8.

With 5 eggs, the number came out to be 7.

I started wondering, could I beat binary search with this method?

I just wanted to see the number of floors you scale when you were allowed 7 drops. Could it exceed 128?

I tried with 6 eggs. Answer? 126.

7 eggs. 127.

Using more than 7 eggs, as expected, gives 127 because max drops is 7. And thus, for the following number of eggs, I had

8? Again 127
20? Again 127.

I then had a look at floors scaled with 6 drops. The answer was 63. 63 appeared the first time (with 6 being the fixed number of drops) when I used 6 eggs.

127 appeared (with 7 being the fixed number of drops) the first time when I allowed myself at least 7 eggs. Wherefrom, it remained 7 regardless of the number of eggs.

Hmmm..Something was brewing in the mathematical universe. The number of floors scaled with a certain number of drops had an upper bound which could not be pushed by upping the number of eggs.

What was going on?

I found the answer in a pdf by Umesh Nair. Though he does not address this issue directly, the treatment he invoked for solving this question could be readily extended to solve my problem.

In particular, he made the interesting observation that if you are allowed a total of 'd drops' then you could not scale more than 2^d floors.

Once I read this statement, it was pretty obvious!

Can you see why?

The answer lies, as Mr. Nair points out, in the innocous fact that for a 'particular setting' ('e eggs', 'n floors', the 'break floor' being the b-th floor) there exists a unique sequence of drops which locates the 'break floor'.

You change the number of 'break floor', you see a different drop sequence emerge. There is, thus, a one-to-one mapping between drop-sequence and a 'particular setting'.

And therefore, the number of drop sequences equals the number of floors you scale for a particular setting.

And obviously, you have scenarios where you do not end up using all of your 'd drops' for a particular setting.

For example, even though in case of 2 eggs and 100 floors, you are allowed a total of 14 drops, if the 'break floor is 1' you can locate it in 2 drops! (not all 14 drops are needed).

Therefore, some drop-sequences are smaller in size. Which means that with maxmium 'd drops' you can really not scale unbounded heights as you increase the number of eggs. Further that bound is 2^d (as remarked above) because some drop sequences being smaller, terminate the entire sub-drop tree that could have been rooted at that position.

Because for the 2 egg, 100 floor, 1st floor-break-floor setting, drop sequence 1st-at-14 and 2nd-at-1 terminates; you cant have, in this particular case (where 1is the break-floor) any other trials after completing your 2nd drop.

This is pretty interesting analysis!

Hats off to Mr. Nair for his work on this problem!

He has made a few other remarks as well. For example, he has converted the original recurrence (which you can also find in my previous post) to a combinatorial summnation.

I will write about that later.

So far, so good.

But that still does not answer why this egg method converges with binary search when number of floors and number of eggs are in binary-search-tandem.

(That is floors are 2^e - 1 when number of eggs is e). In case, you are not sure it does, think a little bit about it; i will not answer it here apart from mentioning that you should be able to make it out from what has been said above.

Call it the tandem-issue.

Intuitively, we would expect someone not familiar with the recursive solution this puzzle boasts of, to come up with the binary search strategy only, given number of eggs and floors are in binary-search-tandem. (In fact, guys usually come up with binary search even when the values are not in that tandem - but that is not what I intend to discuss).

The fact that one comes up, on an intuitive level, with binary search given the tandem complimented with binary search information-theoretic content, maybe reason enough for someone to point out that this solves the tandem-issue.

But such a reasoning is not complete. We need to answer why in binary-search-tandem settings, does the recurrence become as good as binary-search itself. We should not invoke reverse reasoning. That is, we should not say that binary search is what we can use in tandem-issues and since it is known to be best, thats what we do.

We have also got the responsibility to answer why our-recursive-way will also proceed the binary-search way. Sure, it could have figured out a different way requiring the same number of drops differently.

Then why did not it do so? Why another mathematical cataclysm?

Now that we are clear on the problem, we solve it.

We just need to show that T(d, d) = 2^d - 1.

Try it on your own. I will answer it soon in this space only.

For now, its goodbye
-Akash

A few algorithmic puzzles

2009-04-10T08:18:00.000-07:00

Hello There,

Today I will be telling you about a few algorithmic puzzles.

The talk basically involves a problem with its solution. So, if you are a reader who wants to try these out before peeking out at the solution, beware.

Also, I would say that unfortunately, one of these puzzles has been made too popular through interview forums and other discussions, which makes the solving techniques used for these kinds of puzzles look futile.

It is my opinion that interview forums should operate a little differently.

Too much digression, now I will come straight to the point.
Below, I present the first of the two questions that I will be tackling in this blog.

Prob.1) Given 2 special eggs and a building 100 floors high, can you dear reader, find the minimum number of drops in which you can find the height after which these 2 eggs start breaking.

Oh yes, the eggs are special in the sense that they wont start breaking unless dropped from or above the threshold height.

Sol.) The key fact here is to realise that you need to prove the minimality of your solution for which the most general approach that you can use is a recursive one.

Infact, in my opinion, for handling discrete minimization/maximization problems, the best way is to establish a recursive equation. Once you have done that, establishing the lower/upper bound is as easy (hard) as solving the recurrence.

Okay, did you try this problem on your own so far. If yes, did you arrive at the first wrong answer most people do (19). Or did you arrive at the correct answer 14?

Whatever you did, probably reading the explanation for 14 below won't hurt. (I will not explain how people arrive at 19).

Well, the first thing we see is that, its a minimization problem. A good thing about these problems is that, they can always be inverted. You can recast it into a maximization problem which maybe (and in most cases, in my experience is) easier to answer.

There is actually a reason for this as well. Maximization problems tie well with out intuition of "overflow". The analogy is that a bucket is said to hold a 'maximum quantity' when adding anymore quantity leads to 'quantity spillage'.

In mathematical terms, you try to show that a set S contains maximum elements with Property P when adding anymore quantity of elements with Property P will spill one or more quantities. (However, there maybe a few subtle issues involved.) More on this later.

A small, but powerful technique.

In this case, the corresponding maximization problem is to determine the maximum height you can scale using 2 eggs and 'd drops.'

Vary 'the number of drops' till the height scaled is greater than or equal to the number of floors in the question.

Well, the above discussion suggests a not-too-hard/easy-to-find recurrence for this problem.

Try one last time before I give it away in its full grandeur.

Let us assume that T(e, d) indicates the height you scale when you have 'e eggs' and 'd drops'

Hmm. I have selected the notation. What remains is notion. As Gauss remarked, it is notion not notation which is important.

But a notation is also good enough as a starting point. Now - the notion.

Well, its recurrence, right? (Notation says so)

Then the corresponding notion is to setup on its RHS another invocation(s) of the same. (Notion)

Clearly it involves using on RHS some quantity smaller than the quantity you begin with so that the recursion terminates.

SO, what can that be? Well you pick an intelligent height, and go for the first drop. And then you have d-1 drops left. Hold it. You can see your recursion now.

After 1st intelligent drop, you can scale T(e, d-1) floors. The intelligent choice must be so placed, that if the egg breaks, then the culprit floor among the floors below is locat-able with 'e-1 eggs' and 'd-1 drops'. That is the intelligent drop is one level above T(e-1, d-1)!

Thus, T(e, d) = T(e, d-1) + [T(e-1, d-1) + 1]

And for recursion termination?

T(1, d) = d.

NOTE: I have not highlighted (maybe even not told)in this problem where does that 'overflow analogy' is. But rest assured, you can find it.

Will post it later, and then remove this note.

Prob. 2) Well, now we come to the second problem. It is from a competition called felicity (organised by IIIT Hyderabad).

The problem asks you to 'maximize' the number of elements in a set S. All of the elements in S come from a set A of natural numbers which contains numbers from 1 to 2000.

But you need to be sure that you do not include a number thrice (or one-third) and five-times (or one-fifth) of some number you already picked. These elements thrice (or one third) and five times (or one-fifth) are called respectively the first-kin and the second-kin of the number picked.

You need to determine the maximal size the set S can be.

Go on, try it! Below I produce the solution.

Sol.) The key fact here is that it is (indeed) a direct maximization problem. We can try to use the 'overflow analogy' as I demonstrate below. As of now I have not tried a recursive solution to this problem myself, but anyways I have put the 'overflow analogy' to good use here.

See if you can arrive at the solution using what has been said this far (which by the way is no hint..but its okay to try with the assurance that you may need to invoke this process, no matter how insignificant the 'place of invoking' is).

Well, if you tried and did not get it (or maybe did not try it at all) here is the solution again in full grandeur.

Ask yourself, when does overflow begin?
The answer is when maximum cardinality is reached, right?
And how exactly do I arrange matters to create it?

It is this question which puts your creativity on trial.
You can begin with a few cases simpler to analyze. For example limit the size of the set A to 10. How big set S can you create now?

The first choice, guys (usually) come up with. is S = {1 2 X 4 X X 7 8 9 X}.
(X indicates the absence of an element.)

Have we achieved true maximality?
Sadly, no.

Hmmm... these guys say that 'overflow analogy' says that placing any absent element into the set S would cause spill and therefore, they claim that they have achieved true maximality.

And this is where we change all the rules. This is precisely the subtlety I talked about earlier. Call it the subtle issue.

You can see that you can make S bigger by removing 1 and keeping 3 and 5 in the set. Thus, the notion of 'quantity spillage' in these problems is of a different kind. Here, your bucket holds maximum quantity when there are no left out quantities keeping which back spills less.
For example, consider one second answer : S = {X 2 3 4 5 X 7 8 X X}. Hell, its no good than the first one.
This configuration (in second answer) is bad as we can allow 'overflow of just one quantity (2) by adding two quantities (6, 10).

A little experimentation shows true maximality is achieved when S is the set with precisely the above modification= {X X X X 4 5 6 7 8 9 10}

You can see that adding any other element leads to 'spillage'. Also, notice that no quantity 'spills less than it contributes'. That is, you can't (in this particular example) add two quantities spilling out just one.

Thus, we have achieved true maximality.

Similarly, for A = {1, 20} the maximal S is
{1(stop) 7,8,9,10,11,12,13,14,15,16,17,18,19,20}.

But, hold your horses. Do you see it?
See what?
An Aha! insight my friend.

The maximal solution outlined above has contiguous elements! Maybe its 2 or 3 sections but within each section, elements are contiguous.

We will prove that you can always arrange matters so that this condition holds true.

First, notice that your examples above for 10 and 20 elements have one thing in common.
Both of them end at the last element.

So we can try beginning in general with the last element. We will create a decreasing sequence of numbers till we hit n/3. We list all the numbers starting from n down to floor(n/3) + 1. Call these numbers Range-1-start and Range-1-end respectively. You can see that Range-1-start and Range-1-end hold a decreasing sequence of numbers.

Next, we make another sequence starting from (Range-2-start) ceiling(Range-1-start/5) - 1 and continue down till we hit floor(Range-2-start/3) + 1.

This way, you go on till you run out of elements.

Creating this sequence for 1st 300 numbers goes like this.

first-sequence: all numbers from 300 down to 101 (inclusive)
second-sequence: all numbers from 20 down to 7. (inclusive, 21 and others are not there as including them would result in throwing away elements of the first sequence).
third sequence - Containing just the number 1.

This way, you can achieve maximality for any n. It seems you have already proved it for its clear enough.

In case you have not, here is one proof. Including any discarded element will cause spill of one or more than one entries and you don't have the bad situation of more elements getting added at expense of fewer getting discarded in the above construction.

Consider the case when A holds 300 elements. Discarded elements are between 21 and 100 (inclusive) and also between 2 and 6 (again inclusive). Putting 'boundary elements' looks like a dangerous idea; we will analyze it later (It is related with the subtle issue). Putting non-boundary elements leads to spillage of two and is definitely wasteful.

Now back to 'boundary elements' (and neighbors). Putting these back spills an element from the first sequence which cannot lead to the subtle issue as the second-kin of the spilled element from the first set is not in any of the two sequences. Putting it back will lead to one other spillage. So it is also wasteful. And there, finally you have seen true maximality.

Also, I will help you with an extample of one boundary element. For example in the case of A holding 300 elements, if you add 100 to the set S, you spill 300. Hmm. can subtle issue arise? And can it lead to inclusion of two elements at the cost of one 300?

No, it won't. For after inclusion of 100, 300's first-kin, you cannot include its second-kin, 50. Including it will spill 10.

This is the general idea behind the proof which can be easily made more rigorous.

NOTE: Some of my friends told me that it was difficult to make the connection between consecutive-ness of elements and the maximality of the set S. I agree.

Also, they say that 'I got lucky' by guessing the pattern with 2 examples which normally requires many turns. And they also say what if the pattern did not hold for long. I could have got stuck.

True. But my answer is that I did not stop at 2 trials (examples for 10 and 20). I tried a total of 20 trials! (From |A| = 10 to |A| = 30)!!

Thats what mathematical problem solving is about. This is what research is about and this is what interview forums do not do. And yes, this is as far from this research as anything might be but my primary attack is not at its unimaginable light-yearish distance from research but it is primarily again at interview forums which do not promote students to think.

They make you more of an analyst and less of a designer.
And the subject was called 'Design and Analysis of algorithms'. Absurd

Enough for now.

There are a few other problems, I would later include in this post itself. Right now, I want to rest.

Goodbye
-Akash

Relative Velocity

2008-03-10T09:27:00.000-07:00

NOTE: This is the last part of Escape Velocity. I call it relative velocity or Escape Velocity 3. Hope you enjoy it :)

Relative Velocity

Eric, Fred and Dorothy were all suddenly quiet. Their celebrations interrupted, they were trying hard to imagine they were not facing what they seemed to be facing. But they knew that the Ostrich defense was as good as no defense. Time was slipping by and they needed to something about it fast.

The fire-alarm was suddenly beeping, bursting its lungs out at the loudest it could and they could tell there was a problem. “It’s the cleaner room” shouted Dorothy. “Oh, I can see that Dorothy”, smirked Johnson. “I ask why –why so suddenly. It was okay when we took off. Wasn’t it?”

“Not the best time for these questions like those, is it Fred?” Eric chimed in. Fred opened his mouth to argue. Eric cut him short “I don’t know about you two, but I did not come here to be baked. There is not a moment to loose.”

In the meantime there had been some concerns over these travelers on the earth itself. The NASA guys controlling the rocket now knew that Eric was in; but it seemed like ages ago though not more than 5 minutes had passed since. They were, all, focused on the control systems instructing Dorothy and her team on how best to avoid their deaths. They knew avoiding deaths was being too optimistic –they were only instructing them on how to delay their sure impending end.

“Open the vault. Shut the cylinders” were among the two prominent orders shouted. Others said “Disengage, disengage now.” One person was heard saying “Eject, for God’s sake.” He was elbowed to keep his mouth shut.

Up on the rocket Eric was already moving to the cleaner rooms. “Shut the cylinders.” He knew the cleaner room –where oxygen was stored in addition to fuels for the way back– could make the rocket as warm as hell and he knew that removal of oxygen cylinders would cut off oxygen supply to the fuels which would thereafter stop burning –an activity he could not fail. Oxygen being a combustion supporter would make this place infernal, helping the fire, which God only knows how, got started. Add to that the inflammable fuel. A vicious circle. His task though immensely difficult, (it bordered on being impossible) Eric thought, was simple. He would just move the oxygen cylinders out of the cleaner room; as fuel cylinders were immobile –if he had time. The big question being –did he have any.

Dorothy and Johnson were earlier confused about how to handle the situation best. But Eric’s immediate switch to action got them back on their feet. They were talking “You try opening the vault Fred. I will try to change our co-ordinates so that we head for some sea or ocean. Atlantic, I think”

And so they were all busy. Eric carried an oxygen cylinder which though heavy could not slow down his fast steps. Johnson had opened the vault and now offered to help Eric in carrying the cylinders. “Go, get the others.” Shouted Eric.

Nodding, Johnson broke into a run. And before he knew it he was carrying an oxygen cylinder, just like Eric did before him (and who happened at the moment to be running past Johnson to fetch another cylinder), fast-paced all the while. This state of affairs continued for a while. Suddenly, Johnson remembered something as he was carrying his second cylinder. “Should I secure this cylinder first. Is their time?” He knew the answer. “Hell no.” He ran after Eric with all the strength he could summon. “Eric, don’t move that cylinder. We need those three for our oxygen supply. Once removed, we would have no oxygen.” Eric pondered over the issue. “Get the oxygen masks. These need to be moved. Inform Dorothy over the Line 3.”

Having informed Dorothy, a panting Johnson came back to find a tired Eric making his way back to the cleaner rooms. “Two more.” They said in unison. But inside the cleaner room, the devil was waiting. The inferno was already dancing close to cylinders. “Run” yelled Johnson. Eric stood confused. “Let me think, let me think” Eric was saying to himself. “There has got to be a way.” Those words were coming back to him “Try harder.”

“Where is Dorothy?” Eric asked Johnson who was busy trying to move two cylinders (now red hot) together. His hands repulsed but Johnson forced them to stay on them. “Leave them you fool.” Shouted Eric. “You know Eric” Johnson braved “this is our only chance.” And then Eric saw it out of the corner of his eye. Johnson stumbled. “Johnson!!” Eric shouted. But before he knew it Johnson ran to a second vault in the cleaner room itself, with his eyes closed.

Eric heard the cylinders bursting. And he was already on his foot towards Dorothy before he knew it. “Fred, oh no Fred.” Breathless from the run, with an oxygen mask not holding properly he decided to keep his mouth shut about Johnson as long as he could. He did not want to present this news. “It’s not the best time.” He thought, gulping a mouthful of air form the mask. Besides, he knew he would not let Johnson die for nothing.

“Onto anything Madam?” asked Eric.

“Yes, we can survive if we can make it to some water mass before the crash.” Dorothy said trying to sound brave. But Eric saw through it. “You mean the crash is sure?” Enquired Eric. Dorothy’s silence confirmed. “Damn” cursed Eric as Fred’s sacrifice loomed before his eyes.

“Calm down Eric. That’s a lesson you taught us. My speeds of understanding maybe slow relative to yours but you need a taste of your own medicine at the moment.” Said Dorothy dreamily, trying to console a crestfallen Eric.

“Relative velocity.” He suddenly remembered. “Relative velocity.” Now talking fast he turned to Dorothy. “Yes madam, thanks to your relative speed, we can outwit this predicament.”

“Relative velocity?” Dorothy repeated confused. “But…”

Eric explained “Trust me madam I will explain it all later.”

And then he told Dorothy his action plan. He would just fiddle with control boards and they would do as he said when he finished counting three.

“Very well. We may try not to die –with you as the lead who has already outwitted death twice. But where is Fred?” Dorothy asked and suddenly found Eric’s being speechless very troubling. “Where is Fred?” She asked now worried. And Eric looked so strange with that glint of sadness hanging from his eyes (which even the mask-gear could not stop) that she knew the answer. She turned around, shaken. Eric came forward to console her but was suddenly stopped short in his tracks as he heard the words “Oxygen please.” He immediately fetched another oxygen mask gear and moved it to a shivering Dorothy….And instead of using the gear for herself, she just passed it on…A standing silhouette of a man took the gear, fastening it on his head. There Fred stood, panting. It seemed hard to imagine how he managed to stand despite of his injuries, leave alone his panting.

After putting the gear on Fred said “Oxygen cylinders have been secured. The emergency supply we are using will not last long. What is your plan?”

And then holding them both Eric pushed two buttons and they were suddenly on a downward course. The rocket twirled around a bit, like a drunkard and again Eric pushed a few buttons. Maneuvering the rocket, Eric turned it to –or he thought he did– to a thought of location and then he began. “One…two…three.” And he pushed the EJECT button.

And before they knew it, they were out in sky…The roiling air twirled their bodies. Swinging, rotating, floating …in the air they splashed in the blues of Atlantic with their life-jackets fastened. They radioed agencies which came to rescue in time.

When asked -what did he do, Eric explained “I knew you blast off a rocket’s part in stages. I was picturing the blast –though a different blast– with us in, I struck upon the solution. The vault was on the upper chamber. Throwing it off by a blast could thrust us in a downward motion. Fred and I had kept a few cylinders there too. Oxygen being a supporter of combustion made the blast more like it. And..zoom…we were on our journey down. With our locations mostly set by Dorothy, I just waited for the appropriate time to eject. Yes, that wait was dangerous. It was possible that we could have been consumed by the raging fire within the wait interval. I took the risk. And of course, I guess had we been a second late, we would be all dead. But before you guys consider this case closed, there is one mystery to be solved.” And while the media persons stood confused, scratching their heads with the pens they held (yes, these people are used to scratching their pens on their notepad and on their heads, both) Eric forwarded the question “How did Fred survive the blast in the cleaner room.” Since, they were all taken to hospital immediately after the crash; they were all unaware of what adventures their colleagues had gone through. And now it was Fred Johnson’s turn as the media turned to him with Eric’s question.

Fred replied, “To a major extent it was luck. You see, I was trapped –or rather had trapped myself- in the cleaner room lest the blast injured others. But their in the vault I saw a way to minimize the effect of the blast further. The cylinder was mostly red hot on the sides and on the lower region which was where some un-burnt fuel had stuck. This meant there would be a blast a few seconds later which would start on its way bottom-up once the cylinder is punctured. I thought if only I could delay this. And I could. Luckily, there was some water in the room, though of course not enough water to extinguish oxygen supported fire. You will always find some water in the cleaner room-vault –this serves as the temperature moderator in the fuel pipes along with neon. This water, though not enough to extinguish fire as I already said, could be filled up inside the oxygen tank so that oxygen being lighter than water would come above it –though it required opening the cylinder and subsequent pouring of water. The escaping oxygen may cause a blast –and that’s what got me injured- but the oxygen inside the cylinder above the water surface-” paused Johnson and then began theatrically, speaking fast “would take time to get heated up –water has a large value of specific heat. And I thought if I am able to survive the escaping-oxygen blasts, I would simply run to save my ass lest I run out of the time the water-specific-heat-shield bought me. And that’s what I did.” Finished Johnson pleased “I am lucky to be here.”

“Wait Eric, I have a question here for you” said Dorothy. What was that relative velocity talk?”

“Madam, actually when you compared our relative speeds of understanding, I remembered my school physics lessons. One of those –the lesson on thrust– thrusted itself into prominence. And I could not miss it. That’s just the small part relative velocity played in this adventure –but a crucial one, I must say”, so finished Eric.

Finally, when Eric came to hear his exploits talked about, he also understood that he had been made an astronaut; that a fully recovered Fred was now the coordinator of fast decision making classes in rocket-in-trouble courses (actually, the name of course was rocket-troubleshooting but Eric preferred his name); and that Madam Dorothy had been promoted for her paper on a new algorithm for locating longitudes and latitudes based on GPS data.

Terminal Velocity

2008-03-10T09:14:00.000-07:00

Note: This blog is dedicated to Brian N Ball, the author of Escape Velocity. I told that story in the earlier blog (in my words). This is my continuation of that story. Definitely this story is not as nice as Escape Velocity, but thats what I intend to do with your help. Please help me in improving the story. Your help is highly appreciated.

PS: I intend to write a part-3. I will call it Relative Velocity..
By the way here goes Escape Velocity - Part 2 - Terminal Velocity

Terminal Velocity

Eric was back from the moon. It was a wonderful trip. He had come face to face with his dream, had wallowed in it, basking in its glory all the while. Coming back to earth was a rather strange trip for Eric. He was feeling nostalgic when he was on moon (as did the other astronauts). But while coming back, he had this sensation –“Will I ever come back to moon? Hell, this is where I longed to be once.”

The other astronauts also felt the same but they were more practical. .In fact, Professor Dorothy even talked about this kind of feeling that was raging through Eric’s mind at that time. “No stunts here, Eric. You don’t want to be left alone on moon, do you?”

Eric laughed. “I feel home. But, I guess the other home is calling now.”

“We feel the same way, Eric”. Johnson added, smiling. “Part of life.” Then they got back to their rocket and once again took off…at an escape velocity. Eric was again administered a dosage of liquefied oxygen which besides making him shiver made him sneeze a little. But this was the only way he could survive the escape velocity acceleration, or in Eric’s words “escape the escape velocity”. And they made it back to earth safely.

Back home, it felt different. He was a hero overnight.

And he also needed to complete his computer science course which he did in style and four months later he was among the toppers of the batch when he received his degree.

“Tomorrow”, thought Eric “I would pay a visit to my future employer house. I would be there and find out what kind of work I would be doing.” He would have kept on planning for tomorrow had he not been interrupted by a sudden phone call. “Is it Eric Andrews?” the caller asked. “You bet” Eric replied. “Well, Eric. I actually wanted to talk to you about a space travel that our agency is planning. We…” stunned, Eric interrupted the man. “What?” “Yes, you heard me right” the man implored “Let me complete. So, as I was saying our agency is planning a space travel and keeping in view that you could be a marvelous hand up there, I think we are in need of your services.” Eric could not have heard a news more nice “And what is your agency”. He enquired. “NASA” the man replied and the conversation went on.

Before he hung up, Eric knew that the man was Amitabh Ghosh an employee of NASA; that he would not need to join the centre of Astronomical Studies for further four months(NASA would help him out); and he learnt that he would be taking off in a week. He would be flying with Dorothy and Johnson again. “Wow! That’s some news” thought Eric.

The state of happy affairs, however, did not continue long. He had to first go through a physical scan which would determine the soundness of his health as he prepared with his to be team to make a second trip to moon. This test would once again devastate his life. After a thorough medical analysis the team of doctors regretfully told Eric that he again had a second problem with his physical machinery which would render a space travel –or for that matter even an air travel- impossible. The doctors told him that an exposure to ultra-cool oxygen had left his insides chilled. His Gall-Bladder suffered the worst. After being chilled it made his life hang on a precarious thread. It could freeze the bile juices secreted by pancreas thereby causing his painful, slow but eventual death. “But, I remember from my biology classes that Gall Bladder is a vestigial organ. Right? I mean, you guys could remove it.” Eric asked perplexed by the new turn of events. He was told that under conditions like his Gall Bladder removal could be dangerous to the other organs as they got more accustomed to cooling effect of gall bladder. Sudden removal may harm them.

But the doctors had another reason which went far behind the Gall’ effect. It was –his arteries were choking; there was far too obstruction in normal blood flow which resulted from him being ice-creamed in his first trip. Eric asked how the oxygen managed to get inside. The answer that emerged was again a kick in the gut. Besides getting in through osmosis and inhalation, oxygen also entered in a large part because of him sneezing.

Eric went to Dorothy. “Madam, tell them I have done it before. I can do it again.”

Her voice cracked with emotion as she said “Sorry Eric. No one can. You are not going to moon. Not now. Not with such a condition. Don’t you see Eric no one can help you. Don’t try your stunts this time. Don’t mess with your body…It will get the better of you.”

Eric sulked. He could not believe this was the way events would turn out. “A happy news turns gloomy.” He thought. “Sad ending, bad story.” It was this thought –the word story- which set him into action. He could remember having heard “This is the boy’s story. He should do something about it.”

And again the fact that he would go to moon was sure. How he would do it was not. He needed to think. He had a week’s time. And he was aware that he was under scrutiny lest he tries to get inside the rocket. Further, Eric knew that this time the security would try keeping him off. He gathered that he was not allowed in NASA over the coming week. “Hmmm…that could be trouble for a feeble-hearted person. I would just have to find a way which leads in to the rocket.” He knew that he was facing a tough situation. He had a weak mitral valve – which could be solved only by cold oxygen. And his arteries were choking and God only knew what was wrong with Gall Bladder. But these problems forbid him from getting exposed to ultra-cool oxygen anymore. And this meant no space travel.

And then he saw through it! A brilliant solution to a tough problem! Again it involved the risk of death. But it was a game he was willing to play for with all these defects he may well choose to die trying to go to space rather than living on with them.

Time sifted like anything –whizzing past in a blur. The D-day was tomorrow. And Eric had got the word of his going to space out to public through some carefully posted blogs and other propaganda. He, as a result, had won some public support. It could not do him too much of a favor except for allowing him a seat with the spectators. When Eric came to think of it, he knew it was worse. He could not do anything with the whole world watching. There had to be another way.

Eric moved to the NASA building the day before launch and though the security was impregnable on all accounts, he broke through it and seated himself inside the trolley room. Earlier he tried to forge an entry by hacking computers. Though a computer genius that he already was, he could not make cracking the NASA passwords fast. Besides there was trouble with biometric passwords. “Shit, I have to wait for tomorrow.” Eric crouched in a transportation trolley. And before sleep would close in, he wrote another blog under the rubric “My Last Blog.” The Blog described how he contemplated and eventually committed suicide. “There are some hard to see through advantages of being a sudden celebrity.” Thought Eric “Prominent in the list is hype.” He could imagine the media already burning with the question of is-it-injustice-to-Eric blowing the issue out of proportions. Eric mused, “That’s a nice cover-up.”

There lying silently in the trolley waiting for it to be ushered inside the rocket when the trolley man pushed it sobbing, mourning Eric’s death; Eric was already working on ridding himself of his physical infirmities. For all he knew Gall bladder was a vestigial organ. He had already got it pruned (though illegally having paid a handsome sum to the accomplice)

The body needed a cold environment because of closeness to Gall Bladder but it could not endure things too cold. No problem! Eric had tried arguably the most dangerous surgery on himself than anyone did in the whole century. He would not let blocked arteries block his way. In fact he planned on using them to solve his travel problem. He knew that in absence of Gall Bladder, his body would need some other coolant for homeostasis or regulation of body temperature. This homeostatic condition could be achieved, Eric thought, by the coolant in his arteries. Could he use it? He read related articles related extensively. He found that artery-leakage was what he needed and he knew what would get his arteries leaking. Among other things that he came to know –one was acceleration which was what he read in a scientific article detailing his (Eric’s own) exploits. With his arteries leaked sufficiently he generated the cold environment his body needed.

Also there was material left in them obstructing his heart which he had to hope that would hold on as he made his travel. After all, oxygen simply blocked his arteries to lower his heart-beat which was already low now. So, he could, in effect travel without oxygen exposure. This was the only risk. And he ran it. The rocket took off without him going unconscious. But this time it was different. This time… it was real “Ow god…What is erupting out of my heart?” Eric panicked. He had a heart-ache. And then a seizure. He could not hold on to his senses. The pain was unbearable. Imagine an array of hundred scorpions biting you all over your body unforgivingly. Your skin turns red and eyes tend to fall out of socket because of a bite on your foot. You sweat profusely and want it to end…Even if it means death. Within moments Eric was vomiting the stuff he could swear he had never eaten. He did not know throwing out once insides tasted this way. But this was not the best time to feel that taste. He fell down weakened. “I am dying. I could not get the better of my mitral valve without oxygen. Dilapidated and dead, that’s how its going to end.” And suddenly he became motionless. And anyone could tell…pale and blue that he was, he was dead.

Johnson could not control a sobbing Dorothy who could not tolerate the death of someone so young now that they had passed the escape velocity acceleration stage. “But why did he jump? He was a fool Fred, I am telling you that. His body could not be found? What are these news guys up to? And what the hell does Eric mean by this” And she read a few lines of my last blog aloud “And I planned with dare. I will jump from a height of 3000 feet. I could not face escape velocity living. Let me face terminal velocity for all that I know of. Let me face it dying.”

“Oh...Eric we miss you.” Sobbed Dorothy harder.

Suddenly she turned around. Fred was looking at a ghost or rather a blog of a ghost. It detailed his most recent exploit. The blog was titled “Terminal velocity and the body which could not be found.”

Eric had gotten back to his senses after spilling out quite a volume of he did not know what. And first things first, he had written another blog describing every detail in painful details –after he recovered from tremendous heart-pain himself. Besides other things, he wrote –

“Terminal velocity is the constant velocity a falling object attains once let free from a great height. Once attained, there is no further acceleration and hence the name. I had jumped in the previous blog (and yes not in real –so that explains why the body could not be found) from a height of 3000 feet. Under its cover-up(for the legendary jump was fake), I attained the terminal velocity and since it is only after this velocity that you can mould your body the way you like (as gravity does not control you totally at this stage of fall), I also tried, speaking figuratively, moulding my body. And I did mould myself back into the rocket…. I attained escape velocity after the terminal…Adventure, sure as hell, continues.”

And while the Johnson and Dorothy were still pondering over what was the meaning of it all, Eric joined them and while they were staring him hard, he offered them both the explanation of how he made it to the rocket again. “But that was a risk I would avoid” said Fred. “But man you sure have a different biological makeup. The substance that you threw up was the coolant that got inside your arteries. The coolant being liquid oxygen which is lighter than blood was what your body preferred to dislodge when forced by the escape velocity acceleration. Voila! I admit…The age of dare is on….Adventure continues”

Suddenly Dorothy interrupted. “Fred, Eric; there could be a problem.” And when they moved unto her, they said in unison “What the…”

Escape Velocity

2008-03-01T19:01:00.000-08:00

Note: This blog is out of context in as much as the big bang theory is concerned...Its just a short story. Hope u enjoy it...(it was authored by Brian N Ball. I try to communicate the story though there are a few changes as I was unable to recollect the original version of the story)....

Eric was just back from the summer holidays. His internship session was about to begin and he wanted to start it in all seriousness for this was the first time he would be coming face to face with an industry. And not just any industry. It was the space industry –or rather- the research center for astronomical studies. He had it carefully thought through. The industry which he selected was the one he had yearned for all his life. Though now almost a computer science student (his degree was due in four months) he had never given up upon his ambition of wandering the depths of space, of walking on moon, of racing with his friends on Mars. And now the first stage of this big dream was closing in.

He had a penchant for studies and another penchant for applying his knowledge to diverse fields. And the list of these diverse fields was always topped by things –rather any thing- that had even a remote connection with space; a connection which people would not talk about or normally even think of, as it required -in their words- a clumsy crow-barring of the worst kind. In fact, these people some of whom were his best friends often mocked his enthusiasm for connecting every thing with space ridiculing him with their favorite sentence – “Hey Eric! Can you give me your crow-bar? Have to kill a shark.” Others said – “That man is never short of crow-bars. You can take as many as you want and he will never ask you to return ‘em”. But his enthusiasm never dwindled and in fact he found a way to stop these comments when he got interested in real shark-hunting and therefore bough a crow-bar. And from then on when anyone asked him for a crow-bar he would start giving them the real thing –a funny sight- for the person asking for crow-bar would often sulk away embarrassed.

His internship was to start tomorrow and he was busy filling forms for the same when he came across a potentially devastating statement saying that people with weak mitral valves are not allowed to be an astronaut. He would not have taken the statement too seriously had he not seen the statement –only one in a hundred thousands has a mitral valve which can withstand the acceleration when one is propelled to space. He got worried and talked to his friends about it. They said “You need not be worried. Why go to space? You are a computer engineer man. You can analyze the data from the earth itself.” “But no” said Eric, “Being there is different”.

“In which sense”

“You will never know”. He replied.

"Okay then, let’s hope the best for the test tomorrow.” They advised. “Or hey champ! Cheer up. If the medicos open their mouth you show them your crow-bar”. Saying so, they burst out laughing. Fuming, Eric left the place convinced that no good would come out of this discussion and he had better wait for the test which he would perhaps, if he had any luck (though he knew he had none) pass. The D-day duly arrived. He was tested and he was sent a letter of regret. How he hated it! The very sight of it took his breath away. He was furious on God, on friends, on parents, on society for reasons he could not fully understand. Hypnotically, he moved to pick up his belongings thinking to go out on a hunt. He picked up his crow-bar. Yes, its time to kill sharks. He was moving past the Proctor-House when he heard him talking to the Warden, “Yes the boy had a real bad luck. If only, we could help him.”

“You know you cannot. I mean, after all it’s about the body machinery. Right? The boy would do better if he would focus on ridding himself of this weakness”, said the warden.

“And what is that supposed to mean? Should he consider a heart-transplant? Eh” asked the proctor.

“No, no. I actually meant maybe there is some other solution around. Maybe he should kind of break-in. There are, I believe always some solutions to all our problems around us. One just needs to look harder when the situation gets more stipulative. “ Clarified the warden.

“And what solution do you find” enquired the proctor.

“Well it’s the boy’s story and he should better think about it” replied the warden.

In the meantime Eric who had accidentally chanced upon this conversation determined to do something about his only dream –of a space travel. He kept listening to this conversation and when he finally moved, he gathered that there was a rocket launch scheduled today. The rocket would go to the moon. And it would transport some of the leading astronomers to the satellite. Not that he did not know this earlier. It was in the papers all the time. But he had forgot it all after that devastating interview today which seemed to have been an year ago, though hardly two hours had passed since.

But now he was a man with a purpose. He planned it –or rather he thought he did. He would be sneaking into the rocket. How would he pull this off, he was not sure. But that he would was sure. He moved to the launch site as one of the spectators, as they were allowed on the launching grounds. But to move on, he would need an access code. And there would be extensive checking with all those cameras and God only knows which other kinds of instruments. Then he hit upon a solution to this dilemma. He would make a run for it once the launch procedures were underway. If he succeeded, he would simply shut himself up in a room where people normally are not supposed to go during the launch –the cleaner room. Every rocket has a cleaner room where oxygen cylinders are stored at a sub-zero temperature. In fact the temperature is so low that you find liquefied oxygen. This serves a double purpose. When the rocket is scheduled to take off this oxygen so released and then exposed to low pressure and a considerably high temperature, due to an initiated combustion, rapidly expands and supports further combustion. Also it allows proper oxygen supply for the astronauts inside the rocket.

Once he was inside this room –when launch procedures would be about to start, Eric thought, he could be on the journey to moon safely. Safely? He mused. He may die of mitral valve problems. But it did not matter. He was ready to pay the price. He may not die after all. And why not try this solution? For, once he was inside the cleaner room, he could as well start oxygen leakage. For fear of cold oxygen, nobody would come inside the room. Yes, this was it –this was his salvation, his solution. Nobody had ever tried the cleaner room before. So, he could rest in peace with his thoughts that security controls for those inside the rocket to go into the cleaner room would be lax.

And when the launch hour ticked near, a menacingly near at one hour before launch, he dashed for the rocket. Dodging some guards, and oh, in fact dressed as a guard himself. (Which he had done after over-powering one and making him unconscious in the process)

He ran into the cleaner room, shutting it close after him. No one noticed. He was glad though his heart continued at a pace which rivaled the fastest race horses he could imagine. And then, the COUNTDOWN!!!

Off, the rocket, was about to take. “Oh, my mitral valve” Eric panicked. Suddenly he heard footsteps outside. Did they know he was in? Will they drive him out? Hell, he had not even cared for his life to see this moment. In desperation he crow-barred open one of the oxygen cylinders and was suddenly drenched in an outpouring of cold oxygen. Imagine being exposed to the coldest thing you can imagine and imagine bathing in a sea of that thing. Even that thought would not give you the shivers which did not last more than five seconds for Eric which were given to him by cold oxygen at -230 degrees Centigrade. The shivers received from an exposure to immediately cold environment can be fatal, so our body shuts itself in that case in a matter of seconds. But those shivers are so gruesome that you cannot have even seen them in movies or documentaries; they can only be asymptotically imagined. Eric knew end was close. And before going unconscious he could hear 3…2….1….0..lift-off.

When he opened his eyes he found himself in a place where he felt light and had a strange happy feeling. Was this heaven? After all he was dead after bathing in cold oxygen. And he was happy, so hell was ruled out. Therefore, going by logic it was heaven. Or was it? When he started moving around he could see a cratered surface stretching for miles and miles around him. He asked himself aloud “Does God leave you in your most cherished place after you die”.

Suddenly he heard a woman “You are not dead, you fool. But you sure would have had I not gone inside the cleaner room in time. We know the story. You are Eric. You wanted to go to Moon and you are here with us. But I must say your solution to mitral valve problem was mind blowing”.

“Eh.” Eric asked “I never solved that”.

“Ow..We thought that you knew that cold oxygen would slow your heartbeat considerably so that escape velocity acceleration does not hasten your heartbeat to a heart-bursting rate. At any cost, your solution was nice and you should know that you have got a bigger fan following on earth than we astronauts do now. They say –the age of dare has not died. It has been restarted through your rash though I must admit bold steps.”

“Do I stay” Eric asked in a fearful voice.

Laughing, the woman replied “Oh yes! You do. Or what do you think. Would we call our mission back once we are here? Though I must say your going back to earth will involve the same procedure, an exposure to ultra-cool oxygen. That’s quite a way to thwart escape velocity acceleration. And it also has inspired a generation to break free of their limitations as they too rise breaking those bondages at an escape velocity…Adventure Continues”.

A Universe, a big-bang

2007-07-20T04:13:00.000-07:00

The story and history of big-bang model of universe is in itself a story rich with human travesties an triumphs. The story involves some theologists, some theorists, some experimenters and some mavericks.

I will be touching very briefly upon the work of these giants(for i cannot do better) as i take you on a tour of big-bang. However, dear reader, i warn you that you read this blog at your own risk because to a certain extent it draws heavily from the material my brain sucled in uniterrupted gulps from the wonderful book on big bang by simon singh. But let me make myself very clear "i cannot better a simon singh."

So with the above in my mind and with me having paid credit where credit is due we ponder over the following questions in silence for a few moments " How can one be sure of this model? why is this theory held as the chalice of modern science? who were the scientists who fought to bring acceptance to this unorthodox theory?"

There are obviously many other questions you can add to the list and we will try tackling most of them. At present the approach which seems only fitting to me, is a historical one. Lets ask ourselves "How could one actually believe that the earth was round"...

This is what i call the tragedy of the situation. In fact, how surprising the notion of round earth seem to us all in our early life!!! But once you get used to it, the trouble begins. Without any proper explanation staring in face this is nothing more than a burdened-but-real-give-in of our minds to scientific progress.

Perhaps the recent fight over Pluto's planat-ic (not platonic!!) status illustrates a case in point. Pluto is a planet if scientists believe so...otherwise its not. The blatant truth is NASA is itself divided among those who say Pluto is a planet and those who say it ain't.

I by no means happen to know whatPluto actually is and by no means do i proclaim to know what truth will emerge after a heated scientific debate. But i know enough to comment on philosophy of good science. In good science, like in any good detective novel, a fact which amazes most of the readers, in most cases, leaves other equally dumbsturck.

In other words whats brain-storming for you is brainstorming for me and usually the vice-versa also holds true.

But, with a round-earth, i believe things differ. We wonder equally and passionately about how earth could be round when kids but when we see satelite photos and other high distance ultra quality online-streaming, we know different.

The story of how roundness of earth was established, sings the unrivalled glory of human victory over human traditionalism. It begins with a Polish named Nikola Copernika. He is better known as - Copernicus.

Copernicus was able to "see" the earth's images with pure thought experiments and aided by sheer logic. That logic was deveoped in Greece, polished in Arabic countries and developed formally from its torn parts into a coherent system by Copernicus.

Long back, Aristotle had commented that the earth is flat and is the centre of the universe around which other planets and sun move in circles. To those of you who think gravitation was not a big idea, it seems best to let you know that at this point of time the falling down of objects to earth was a fact readily explained by earth's centrality.

However, Aristoragus, a contemporary of Aristotle, saw a problem. He knew that earth was the centre of the universe - thats okay so far. He expected everything to move around the earth in perfect circles - thats okay. What was not okay, was the fact that planets close to earth -mars and venus- moved in a strange way. They seemed to be exhibiting retrograde motion

This horrible name is understood quite simply. Actually this motion is what you can expect to see if you are watching a object cutting a circular path nearby. (the object is not circling you but circling something different. In case the object were to circle you, you will see uniformity in its motion. It will never speed up or slow down.)

But this is what Mars and Venus did. And if Aristogarus was thinking along the right direction (which he was) probably earth and mars were both cutting circles. Those circles could be around anything (not necessarily same). However, this idea was rejected, slayed by hypothesis of famed Aristotle. Still there were some who held this idea in a serious vein until they met Plato and his epicyles.

Whose fascination!!!

2007-07-08T03:45:00.000-07:00

In what follows, (so it has already begun) the readers of this blog (if any) will, or at least should, bein to appreciate if they are not doing it already - the power of a fascination, that lasts. The first obvious question is - which fascination. It is needless to say that other questions like whose Fascination, why fascination follow in the first place.

But since i decided to write about a generic fascination, i named this topic as whose fascination and not which fascination. Note again- the answer to whose fascination is the fascination of the mass.

Having answered the second question, its time to tacle the others; or wait- is it? "Fascination of the mass" - does not that thing deserve a little elaboration? Since i feel that it does, i delve into it.

Our lives are dictated by mostly a desire to find meaning. It is fuelled by a sense of making sense out of what we do and our surroundings/environment does upon us. A simple action-reaction pair. So the fascination which lasts, if it is to be fascination of the mass, it needs to address these basic philosphical questions. what questions? Questions infact related with our action-reaction system and thus connected with our surroundings.

What can be the answer? This is interetingly the first question...Which fascination? and the answer is science...A universe. A big-bang...A theory..A reality...Creation...Miracle..It is this sense of human achievement which i will be detailing more upon in my future blogs. The human history sings this single basic theme. Everybody forms his own theories of being. Not that this is wrong. this is what one must do or else he will be no better than a stone. But taking into the accoun the bewilderment, excitement and tragedy which surrounds one of the world's greatest discoveries, i feel it is imperative that we look down the tunnel created to understand self by the giants of human race...A tunnel we need to look into..A tunnel we need to get fascinated by...A tunnel which tells - why fascination.