The Right Way!

It’s been an amazing March and the journey so far has been exhilarating. Fighting dragons, crossing bridges, running races, going in “Strange Loops” etc. Looks like an excerpt from a fairy tale adventure except for the fact that the prince (supposedly me) is definitely not living happily anymore. Big thanks to a couple of colleagues (that includes my mentor Mr. Pai) who helped open the window:

CreateWindowEx(
        WS_EX_CLIENTEDGE,
        g_szClassName,
        “Hello Linear-Programming”,
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT, ∞, ∞,
        NULL, NULL, hInstance, NULL);

Well! It all started when my colleague got this wonderful problem from his friend. It went like this:

“What would be the maximum messages that you could send using any given number of senders and dispatchers with varying capacities plus other defined constraints?”

This was the “Larger than Life” generic version of the problem that we yearned to crack. The real problem (the one I believe I have solved rightfully below) was too tempting to be conquered, especially after having slain the dragon (I was able to contain a trojan-horse in my PC without having to forfeit/format my kingdom/hard-disk), I ended up with a naïve procedure that of iteratively, proportionally dividing the load based on sender/dispatcher capacities. My mentor knew from day one that, this was a classic Linear Programming (LP) problem (which I couldn’t fully comprehend then) and he was quite adamant in trying to get this solved “the right way”.

Thus began my captivating journey on Mr. Well’s “Time Machine” across Prussia, along with Euler trying to cross all the 7 Konigsberg bridges “exactly once” (Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani) and Greece, where I pitted against the tortoise in place of Achilles trying to prove Zeno wrong and then going in “Strange Loops” over Escher’s paintings (Godel-Escher-Bach: An Eternal Golden Braid by Douglas R. Hofstadter). And finally after pounding through various other Finite Mathematics & LP books ranging from (A Beginner’s Guide To Finite Mathematics: For Business, Management, And The Social Sciences by W. D. Wallis) to (Linear and Nonlinear Programming: International Series in Operations Research & Management Science by David G. Luenberger & Yinyu Ye), I finally was able to comprehend the problem at hand, and more importantly confront the beast that we intended to leash, “the right way”.

The Problem:

Three senders S1, S2 and S3 can send 50, 100 and 60 messages respectively. These senders need to consume three dispatchers namely D1, D2 and D3 with message capacities 40, 80 and 60 respectively. Determine the message distribution across the senders and dispatchers for maximum throughput provided:

  • S1 can consume only D2 and D3 for sending messages
  • S2 can consume only D1 and D2 for sending messages
  • S3 can consume only D1 and D3 for sending messages

 

:: My Take On It ::

The problem has been modeled into the following matrix and LP problem as shown in figure below:

The Problem Matrix In LP Terms

The Problem Matrix In LP Terms

I have adopted the “Simplex Method” for solving it as shown in figure below:
The Simplex Solution

The Simplex Solution

:: And now we have the distribution with maximum possible messages (180) as shown in figure below::
The Distribution For Maximum Messages

The Distribution For Maximum Messages

In case, you are still wondering why I live unhappily, you need to take a look at the “size” of the window again that my colleagues have opened.
Yeah it certainly is Infinity ()!

Advertisements

ecnalG

Still wondering what this title means???

I can see the wry smile on your face telling me “No Big Brainer Dude!”
I know how easily you would have cracked this word Jumble. But, how many of you ever wondered why the “Jumble” was arranged this way? Well! There’s a reason for everything. I never thought I would carry this as a blog title when I was solving this “lateral thinking” (the one where you are supposed to think out of the box) puzzle a couple of months back.

The title indeed is “Backward Glance” and not just “Glance”!

I believe it is more difficult to frame a puzzle than solve one. Note the use of word “frame” rather than create. Language plays an important role in encoding the clues (both wanted and unwanted) that lead to the cipher (solution in our case). Dexterous encoding creates “intended” diversions and confusion to the reader. But remember the cipher is lying there to be discovered “beneath” framed layers of clues (information). We normally tend to leverage just our innate X-Ray vision (a.k.a. pragmatic mind) to look for the cipher “through” these layers of clues rather than giving a “Backward Glance” (Slide these layers aside and directly look at the cipher beneath) at it.

Let’s try to decode the title:
Real Clues:

  • It is a “simple/easy” Jumble (credit to my intuition or IQ)
  • The Jumble is arranged directly by “writing the word backward” (this is the most important clue which a pragmatic mind tend to overlook)

Diversion:

  • It is “just” a Jumble (blame it on my egoistic IQ)

See, it works! There’s no harm in taking a backward glance at the problem when you feel you have reached a solution. This “Out of the Box” approach sometimes helps unearth the vital clues that lead to the right solution. I will try to illustrate this further by taking on these two famous puzzles. Well! I have given you the most important clue by now.

Please see if you can crack it with a “Backward Glance” before attempting a “Forward Glance” at my take.

1. The Bicycle Thief

Here is a little tangle that is perpetually cropping up in various guises. A cyclist bought a bicycle for £15 and gave in payment a cheque for £25. The seller went to a neighbouring shopkeeper and got him to change the cheque for him, and the cyclist, having received his £10 change, mounted the machine and disappeared. The cheque proved to be valueless, and the salesman was requested by his neighbour to refund the amount he had received. To do this, he was compelled to borrow the £25 from a friend, as the cyclist forgot to leave his address, and could not be found. Now, as the bicycle cost the salesman £11, how much money did he lose altogether? (Courtesy: Amusements In Mathematics by Henry Ernest Dudeney)

:: My Take on IT ::

The entire problem ingeniously encoded beautifully boils down to:
Real Clues:

  • The cheque provided by the thief was “valueless”
  • The Real cost of the bicycle to the salesman was £11.00
  • The money that the salesman gave to the thief was £10.00 (as change)

Diversions:

  • All other information

:: The equation is very straightforward now! The total loss for the salesman was £21.00 (£11.00 + £10.00)! ::

2. The Missing Dollar

Three people are eating at a restaurant. The waiter gives them the bill, which totals up to $30. The three people decide to share the expense equally ($10 each), rather than figure out how much each really owes. The waiter gives the bill and the $30 to the manager, who sees that they have been overcharged. The real amount should be $25. He gives the waiter five $1 bills to return to the customers, with the restaurant’s apologies. But, the waiter is a dishonest man. He puts $2 in his pocket, and returns $3 to the customers. Now, each of the three customers has paid $9, for a total of $27. Add the $2 that the waiter has stolen, and you get $29. But, the original bill was $30. What happened to the missing dollar? (Courtesy: Jim Loy)

:: My Take on IT ::

The entire problem ingeniously encoded beautifully boils down to:
Real Clues:

  • The Actual Bill was $25.00
  • The 3 people spend altogether $27.00 ($30.00 – $3.00)
  • And the waiter took $2.00

Diversions:

  • All other information

:: The equation ($27.00 – $2.00 = $25.00) is very straightforward now! There is no case of any missing dollar here! ::

Never underestimate the power of A Backward Glance!

Probabilistic Bliss

This day that year :: 1989

Mathematics had eluded my senses (both common and uncommon) and I was literally treading this pathetic path (identifying problem patterns and memorizing its solutions). It was destination “disaster”. I was traumatized and the probability of a success was merely 0.5

This day that year :: 1990

An apple fell. I should say it literally broke or rather rewired the entire logic circuits of my psyche. I was so glad it fell unlike Mr. Newton who thought why it fell though I felt it fell late (better late than never, right?) I began to reason, analyze and attack the problems. I should confess that I became passionate, obsessed and finally possessed by Math.

This day this year :: 2009

Almost 2 decades. Mathematics rules my senses today. Till day, I don’t really know how this Boolean State Transition (0-1) occurred that too in such a short span. I attribute this success primarily to Mohan sir (my tutor) and to an unseen, unknown force (let me call it God) who, for a purpose, made this happen, which I am still in pursuit of.

Last weekend, I was flipping through the pages of a book on Discrete Mathematics that I bought (thanks to one of my mentors Pai for recommending this book) recently. And I stumbled upon this chapter on probability. It was a feeling that I cannot express through mere words. It was mere bliss as I laid down the Lego Blocks of knowledge one by one and I am sure that I did come up with the most beautiful structure that Richard Johnsonbaugh would have envisioned his reader to create.

Now with this confidence (or rather an element of defiance/arrogance, if I am to confess), I decided to try my fortune on the “Monty Hall” problem. It wasn’t that late before I joined the huge majority that failed trying. My obvious answer was obviously wrong. Hey! At least I tried. I tried to reason where I went wrong and read the solution that was illustrated in detail. I could very easily understand the rationale behind the solution (which is arguably been contested by many as confusing). Thanks to my foundation on probabilistic analysis that was re-solidified by Johnsonbaugh. I would like to share my take on it with the hope that it sheds light to any confused soul.

Monty Hall Problem

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (courtesy: Wikipedia)

:: My Take on IT ::

The key to the solution is to ascertain your best odds of nailing the prize with the choice you had made, assuming your chosen door has the prize hidden behind it, based on the 2 options that you have.

Option 1 (We decide to stick with our initial choice)

Remember the “key”, I had outlined above. Based on this, we would opt for Option 1 because we believe we chose the door with the prize behind it. The probability of choosing “this” door out of the 3 choices given is quite obviously 1/3.

Option 2 (We decide to change our initial choice)

Remember the “key” again. Why does one need to change the initial choice? Because, he/she believes that the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) has the prize behind it.

With this assumption our initial choice (say first event in probability world) had left us with a winning probability (p1) of 2/3 (i.e. the door with the prize is one among the remaining 2 non-selected doors out of the 3 choices). Now, here comes the crucial step in this experiment. The host (unlike in Option 1 where his/her action doesn’t affect the result) is actually telling us something very important i.e. the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) holds the prize in this case. And we can confidently pick this door (say second event in probability world) with a winning probability (p2) of 1 (certainty). So now, as the experiment is fair and the events are independent, the probability of the entire experiment would be (p1 * p2) i.e. 2/3.

Conclusion

To conclude, let’s analyze our findings on options 1 and 2.

  • Assertion 1: The chance of winning with Option 1 is 1/3.
  • Assertion 2: The chance of loosing with Option 1 is 2/3 (1-1/3).
  • Assertion 3: The chance of winning with Option 2 is 2/3.
  • Assertion 4: The chance of loosing with Option 2 is 1/3 (1-2/3).

Now, do I need to tell you what to do? Yeah! You guessed it right. The Assertions says it all!

:: It is best to switch your choice (Option 2) to increase your odds of winning the prize ::

Well that wasn’t that difficult, right? I guess not!

And, if you still find it confusing, please try visiting this site which helped me understand this solution to the problem.