Roommate's dilemma [modified version]

This blog is about explaining the simple, yet very interesting puzzles which I categorize as puzzles under Game Theory.

Here is a small modified version of prisoner's dilemma :

Me and my roommate live in an apartment near our university. I come home to see that the apartment is dirty. There are soda bottles, empty pizza boxes, dirty tissue papers and all sort of dirty stuff lying all around. I definitely don't like it when the apartment is that dirty. I can still live as I am in the apartment for a very small amount of time. What should I do ???

Let me assume this :

We are in the same class or we develop a good rapport. We both have equal amount of work and have exams and holidays at the same time. There are greater chance that we get time to know each other. I can talk to my roommate and arrange a schedule when we both can clean up the apartment once in a while or any similar strategy.

Now the things become very simple and the apartment is clean and we are happy (so is the landlord who occasionally checks the state of the apartment, he is really happy and offers a discount on the month's rent !!!!! ). We both have lost some time.

Now imagine if the things were a little different :

We are not in the same class or we are introverts. We do not talk much with each other. There is no communication. If we observe this situation, we see lots of interesting things :

I come home and see that the apartment is dirty. I don't talk to the roommate and I don't like the apartment being this dirty. I can either clean up the apartment myself or wait for the roommate to clean the apartment. These actions have a different possible outcomes. If I clean up the apartment myself and keep the place clean, the landlord sees that the place is clean and offers some discount in the rent. We both end up paying lesser money / saving money. But, why should roommate get rewards because I cleaned up the place ? Why should I do all the dirty work and both get rewards ? I also have lost lot of time cleaning up the place. I could have done something really useful in this time. It is rather unfair.

I could choose to not clean the apartment and wait for the roommate to clean it up. If he cleans up the place, then I get the discount in the rent and I wouldn't have wasted any time cleaning up the place. I could do some creative work in this time. Landlord will definitely be unhappy and will not offer any discount.

Observing this situation what should be my best course of action ?

Game theory suggests that NOT CLEANING THE APARTMENT is the best course of action !!!!!!! How ?? Technical aspects will be covered in subsequent posts ...

Joker's action in the movie of Dark knight is an example of Game Theory. As quoted by Prof. Benjamin Polak of Yale university, these people are called "evil gits". So is game theory teaching us to be 'evil gits' ? Hmmmm .... I will post more of my thoughts in the coming entries ...

I will discuss more about this in the coming posts. HERE is the original prisoners dilemma puzzle.

This entry was inspired by this lecture.

The weird problem of MONTY HALL

Today I am going to tell you a story.... A story that I felt was weird ... It is about about the MONTY HALL. Here it goes .....

Here is the Problem. I am in game show. The rule of the game show goes something like this. There are three doors. Behind one of the doors is a car. Behind the other two doors is a goat. So totally there are 2 goats and 1 car. Whichever door I choose, I win the thing behind it. I would certainly want to win a car as I am not interested in the goat. Even if I do win a goat, I win something and I am not completely unhappy.

So I am asked to pick a door. I pick door '1.'. Ok ... My chance of winning is 1/3. 33.33% of winning a car. I keep calm. 

Now there is a twist in the game. The game hose declares another rule. He decides to give me another chance but, this time with a twist. Door numbers 2 and 3 are unpicked. He now offers to open one of the doors 2 or 3 behind which is a goat. He opens door 2 and there is a goat. The game host now gives me another chance. I can either change my door selection or I can go with 1. I calculate that the probability of me winning the car is 1/2 or 50%. A much better probability, but it doesn't really depend if I actually change my option. I still will have 50% chance if I choose either of the doors. I stick with door no.1. The game host asks me if I am sure and I say I am. The game hose opens the door and there is a GOAT !!!!! I had lost the game .... Behind the door 3 was the car !!!!!

What went wrong !!!! May be analysis was wrong or my luck was bad !! The guy after me also lost. So did the guy after him. The guy after him won ... There was nothing wrong with the game I guess ... My luck and analysis was bad was what I thought ....

More careful analysis reveals what went wrong and why !!! The explanation is very simple and should be viewed as a whole and not individually. Then it becomes clear as to where I went wrong ......

The first mistake : What I saw was that the probability of selecting a car was 1/3rd and what I did not see was that, inspite of 3 doors, the probability of me selecting a goat was much higher. it was 2/3rd or 66.66%. So, it now became clear to me that 2 out of 3 times I would have ended up selecting a goat and not swapping next time would clearly be a big mistake !!

The table below shows as to why changing the selection is a good idea. Interesting the chances of winning goes up from 33.33% to 66.66% if you swap. (Refer the figure below as to why)

Now that this problem proved that swapping is actually a good idea, I started thinking about the personality of the people in the game and their winnings. A person who seems to be a stubborn kind (one who sticks with his choice) will end up losing while a person who seems unsure and doesn't really know what to do and changes his option will end up winning 66.66% of the times.

Ramesh's Bus Problem

I am reading a few interesting scriptures on Algorithms. As I come across many algorithms which solve spcific tasks related to various problems, I started wondering if there is any 'Best' way of solving my 'Bus traveling' problem.

This is the problem I face everyday and I follow a certain way to tackle this problem. It is actually somewhat interesting if you are a frequent traveller using public transports in India.

My mode of communication from my home to office is public transport buses (BMTC - Bangalore Metropolitan Transport Corporation). The frequency and timing of the buses are erratic which I will define as the 'Degree of erraticity'. I generally have to change buses at three different points. I begin from my house and the bus stop near my house is the first place. I have to go to Bangalore Central Bus Stand which is my second. From there I got to another place called Marathalli which is just 1.5 kms from my office and I board a bus from Marathalli and reach my destination. I stay nearly 22 kms from my office. The distance from my house to Central Bus Stand is nearly 4 kms. Distance from the central Bus Stand to Marathalli is 16.5 Kms.

Now regarding the frequency of the buses. The frequency of buses from the bus stop near my house to Central Bus Stand is atleast one every 5 mins. This is really erratic. Sometimes, more than one buses to the same Central Bus Stand come one behind another and there is a small war between the buses as to who reaches the destination first. Sometimes, I would have to wait for nearly 15 minutes at my bus stop to get a bus to Central Bus Stand. It takes 15-20 minutes to reach the central bus stand from the stop depending on the bus. I have observed that there is atleast one bus between 6:10am and 6:15 am for certain. Sometimes, there are two and one of these two is really fast and I can reach Central Bus Stand in 15 minutes.

Once, I reach the Central Bus Stand, I have two option. There is a bonus bus which takes me directly to the office from the central bus stand and the frequency is very low. The driver of this bus is drives at normal speed and I can reach office in 40 minutes. One every 40 minutes is the frequency. There is one of such buses which leaves Central Bus Stand between 6:25am and 6:30 am. Once every 3 days he is really late and leaves the Central Bus Stand at 6:40. The route number of the buses plying between the Central Bus Stand and My office is '333W'. While, there is another option, which is the more general. I will have to get into that bus ,get down at Marathalli and board another bus from Marathalli to reach my destination. The frequency of this bus is pretty high. 2 buses every 5 minutes. But, there is a catch. I have observed that a few bus drivers drive the bus fast and I can reach Marathalli quite quickly compared to other bus drivers who drive at the normal speed. The extra overhead time if I travel in the buses which are driven by slow drivers is around 5-15 minutes. If the bus is fast I can reach Marathalli in 30 minutes. The route number of the buses plying between Central Bus Stand and Marthalli is '335E'.

From Marathalli to my office, distance is around 1.5kms. I will have to board another bus from Marathalli. But, the frequency is really low. One bus every 10 mins. But, I have an option here where I can get into a private cabs and reach the office, but, this comes at an extra cost. The extra cost is negligible, provided I do not take this option everyday. It takes 5 minutes to reach my office from Marathalli. If I leave my home after 6:30am the time each stage takes gets increased by 10 minutes.

Provided these conditions only, what is the most efficient way of travelling to Office ?

This is the problem I face everyday and I follow the following method to reach the office:

I reach the bus stop no matter what, between 6:10 and 6:15. I reach Central Bus Stand. I start searching for 333W, the direct bus to my destination. If I do not find the bus, I get into 335E. I reach Marathalli. Once, every 2-3 days I wait for 10 minutes to get a bus to reach my destination. Once in a while, if I am lucky, I get the same 333W which would have left late. Once in a while I take the private cabs. Is this the best solution or do better ones exist ? Can it be proved mathematically ???

This problem becomes more interesting once we start thinking more about that. Answers anyone ?? :-)

My first course in Algorithms - (As an instructor)

Although I have given a few seminars and spoken to a large gathering quite a few times, teaching in class for one full hour is a a complete joy. I requested my professor to give me an opportunity to teach the students of electronics branch about algorithms. Algorithms as a core course is not present in the electronics branch and hence, my professor Mrs. Geetha Prakash was also willing to let me teach. Today was the first day of my teaching. A lot of the guys who were in the class seemed disinterested but, I knew that would be the case since I was also completely disinterested in a few classes when I was a student in PESIT. But, I was glad that the mojority of the class was interactive. I knew a monotonous kind of teaching would certainly put people to sleep (as it happens in most of the meetings in the companies). So, I decided to throw in a few puzzles to the class and tell them something interesting so that, they would keep thinking and their attention did not drift towards anything else.

One of the things that I told them was the history of the 'e'. I also told them how did the logarithm table work. It is interesting that most of the students do not know how the logarithms work. When we were in our High School, we were asked to work out everything using logarithms. Calculators were banned in classes and examination. Everyone in today's class knew how to use logarithm table but, interestingly very very few seemed to know how it worked.

A * B / C had to be calculated and A, B and C were large numbers. They know how to get the answer using the log tables. Use the log tables (to base 10 ... Which few seemed to know) and get the 'magic' logarithm values for A, B and C. Add the log values of A and B and subtract the log value of C. Then use the anti-logarithm table and get the final answer back ... ta daaaa ... Magic !!!!

Converting a complex multiplication and division to a very simple addition and subtraction seems to be a magic. But, behind the log tables is a very very simple technique which any High School student if given the task properly can accomplish. Yes ... A high school student can write a log table. It was 6 years ago that I was fascinated by the log tables and thought that the inventor of the log tables was a magician. When I expressed this to a very very good friend and a mentor of mine, he laughed and said, there is nothing great about it.

Any number can be expressed as a power of any other number. When we hear the base of the algorithm being 10, it means that the number A is expressed as another number 10 ^ x.

A = 10 ^ x
B = 10 ^ y
C = 10 ^ z

A * B / C = 10 ^ (x+y-z)

Hence, we add the log values of x,y and subtract z from it. When we have to find anti-log, we just raise 10 to the power of (x+y-z) and there comes the answer. Interestingly, everyone in the class was able to understand (if not appreciate because of its simplicity). Everyone knew what was happening in each step and everyone had done things like this before. Only thing that made the difference was the inability to link it and come up with a conclusion.

Similarly, when I explained insertion sort and asked them to write it in the form of algorithm, they seemed apprehencsive, but, when I started writing the steps they came up with the next step. I began to realize that, inspite of students being very intelligent and very smart, they were a bit apprehensive... May be due to lack of confidence. I am not sure. But, explaining insertion sort was fun. There are a lot of places where insertion sort is explanined with animations, so, I wont be writing about it ... I found the following like very useful and informative

 http://www.sorting-algorithms.com/


Most of the students knew that,
e = lim (1 + 1/n) ^ n as n tends to infinity

(value e = 2.71828182845904523536028747135266249775724709369995...)

It seemed to have weird resemblance with compound interest formula.

If the interest is compounded q times a year: A = P(1 + r/q) ^ nq


When I googled a bit for it ... Indeed ... I was correct... It did have it's root in bank. Jacob Bernoulli seems to have come up with this constant when he was calculating compound interest. He came up with the above number.

I will write a few more blogs on algorithms in the subsequent entries. Mathematics has always astonished me. It remains the best subject to study. When I get depressed or the day doesn't go fine ... I deal with them by reading up a few math stuff ... And it always works !!!