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 !!!

Mathematics behind Tick-Tack-Toe

I am pretty sure almost everyone would have played this game. It either ends up in a draw or the person who is a stupid loses. The winner need not be intelligent,but, the loser has played the game very badly indeed. What is the logic behind winning ?

1. You make the first move
2. The person on the other side is dumb. (Yeah !!!)

This is a game where one can never lose. Since, this is a game where one can never lose, it is not a game at all.

When will the person win you ask ?

When the 'O' is in the centre and the 'X' is in any position other than diagonals. If the second move of X is in any position other than the diagonals, he is bound to lose.

You can never lose .... You can call a draw when the second move is on diagonals....

I had played this game endlessly when we were in school trying to prove the opponent that I was smarter than him. A few times I used to win and a few times the person on the other side used to win. Now, i realized that we weren't trying to prove who is smarter, but , we were trying to prove who was dumb. 

The Logic :

There are initially 9 places you are allowed to choose. 8 lines totally available to both the players to complete.

Step 1 :
The player1 (Green) who goes first chooses the center point, because he has the possibility of completing at least one of the 8 lines. Any other point he chooses he would be giving himself a lower probability of winning.

Step 2:
The second player(Red) has the remaining 8 points at his disposal. The move that he makes decides the fate of the game. If he chooses any point other than the diagonal he will lose. By choosing the point on the diagonal what the player2 is doing is undoing 3 of the winning lines.

Smarter move

dumb move

choosing any other point not on the diagonal would eliminate not 3 but only 2.






Step 3: Assuming player2 has made a smart move., now the player 1 has only 4 lines left to be completed. His next move will most obviously be directed towards making two straights so that he can finish off the game. But, unfortunately those moves can easily be blocked by the opponent.

 : Target Win :

Step 4: Easily these moves can blocked leaving the player1 with no option but a draw. But, the dumb move always presents the player1 with an opportunity to win for sure. 

The figures show the steps that will be followed by the player1 to actually win the game. Now after the last step, player2 is left with one move but to block 2 of the winning lines of player1. This would never come into the picture if the player1 had chosen the diagonal point as the first move. The game of tick-tack-toe is NOT A FAIR GAME. Every game, any move of any two players, for the first two moves can be such that the game results in a draw and not a win. 

Now, are other games too similar to the ticktacktoe.Can the result of the game be determined even before the game is played. Are all games such that, it's not the smartness of a person is measured but, the dumbness of the opponent. If the opponent is aware of the symmetry of the game, he could never lose. 

One version of complete stupidity is given here :

http://en.wikipedia.org/wiki/Tic-tac-toe

I really can't believe people think of this game as A REAL MATHEMATICAL PUZZLE. It is something of no practical importance and is a waste of time spending more time that the time required to read this blog entry. 

:-D .. Hahaha 

Prime due to a reason

---------------------------------------------- From the past ---------------------------------------------

Before starting off with another beautiful topic of "Prime" numbers let me try and convince myself why does table of 9 exhibit symmetry.....

9 X 5 = 45   - 9 X 6 = 54

9 X 4 = 36  -  9 X 7 = 63

9 X 3 = 27  -  9 X 8 = 72 

9 X 2 = 18   - 9 X 9 = 81

9 X 1 = 09   - 9 X 10 = 90

a two digit number can be expressed as (10x + y). Since, 10x+y is divisible by 9 as in the case above, so is (10y+x).

Ex : (Representation of a 2 digit number xy as 1x + y)
xy = 10 * x +  y
45 = 10 * 4 + 5
36 = 10 * 3 + 6
72 = 10 * 7 + 2

In table of 9, 45 and 54 both are divisible by 9 . similarly 72 and 27 .... etc

Now, 10x + y, i.e 27, 45, 54 , 72 is divisible by 9.
Since it is symmetrical 10y + x is also divisible by 9.

Observe that the sum of the digits is always 9. (Proof of which will be given in subsequent posts)

=> x + y = 9

=> 10x + y = 9x + (x + y)
=> 9x + 9 = 9(x+1)

9(x+1) is obviously divisible by 9, which leaves quotient as x+1. This result is also very interesting. But, we will leave table of 9 here ............. Let move to the most interesting of all .... The prime numbers

-----------------------------------------End--------------------------------------------------------------

1. Introduction to prime numbers and very interesting fact about 11,13,17 and 19...

Prime numbers are some numbers which have factors as 1 and the number itself. (Text book definition)

I never quite understood the concept of factors. I looked at it this way .... Prime numbers are those annoying numbers which never get divided.

There are some interesting thing to observe about prime numbers. They always end with 1 or 3 or 7 or 9 .

it can't end with even numbers and 0 because it would certainly get divided by 2. It can't end with 5 because it would get divided by 5. Remaining are 3,5,7 and 9.

Proof you ask ??
Proof : 11,13,17 and 19. (Isn't it weird that these are the continuous primes with same digit in 10's place. Does any sequence exist with same 10's place yet there exist 4 primes.)

2. Why are they prime or at least called so? (If I were to name them ... I would have named annoying numbers or freaks )

Ans : Definition of prime number by Euclid (Tougher than text book ones)

or

Prôtos arithmos estin ho monadi monêi metroumenos.

or 

Prime numbers are that unit alone measured.

or

A prime number is that which is measured by an unit alone.

 (Souce : primes.utm.edu/notes/faq/WhyCalledPrimes.html)

well, it is pretty simple :

Every number always have least mulitples as prime numbers : 

Ex: 

1> 64 = 2*2*2*2*2*2 (Well, 2 is the only even prime number... you knew it already !!!)

2> 33 = 11 * 3 

3> 96 = 3*2*2*2*2*2

All numbers have least mulitples as prime. (They call these as factors. Least divisible factors are prime numbers. Hence it is prime.)

3.Story about prime numbers

There is one puzzle which many mathematicians are trying to break. It has so much significance that, any person who solves it can get 1 million dollars. It is P vs NP problem. The mathematicians all over the world are trying to prove whether 

P == NP (Is P equal to NP) or P != NP (P not equal to NP)

If N =1, then  P == NP !!! Right ? Where the hell is my 1 million dollar?? (?????????!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I may get killed if any P vs NP enthusiast reads this)

Jokes apart ,

Actually it is too complex to even understand. P is one class of problems and NP is another class of problems. They are trying to see if they can actually be segregated that way. I will try to explain in common man's language (as much as I have understood ... I might be wrong .. Who cares !!!)

P Problems :: These are the problems which we can solve easily following some algorithm. 

Ex: go on a date, add two numbers, multiply two numbers, sing a song etc ...

NP problems :: These are the set of problems which are too difficult or nearly impossible to solve. But, given the solution it can be verified whether it is correct or not.
Ex:  will she accept my proposal?, find the factors of a number which is a product of two very huge prime numbers(one which matters here !!), did people like my song ? etc ..

They are trying to see whether P == NP or not. (Don't take the examples seriously .. It was just to give an idea)

Given 14160, it is easy to find the factors (since it is obvious that it gets divided by 2 and find the subsequent smaller numbers)

But, Is it easy to find factors of 14161 ? Difficult right ?

 Now i say :

It is actually 119 * 119 .

You can verify the result easily. 

A system similar to this is used in many bank security systems. This is thought to be a NP problem. If they prove that, it is infact P ... then I can follow a few steps of some algorithm and break all security systems in the world. There will be chaos.... Sadists are trying to prove that P != NP ... If P == NP, there will be so many new things ... (Recent proof by Vinay deolalikar of HP labs has given a proof that P != NP and mathematicians say that the proof is not too legitimate... I have no idea about their arguments .. So, lets just stick to prime numbers.)

4. Are there infinitely many prime numbers ?

The answer is yes. The solution is very simple. 

Assume that there are finite number of prime numbers.

Let me state 2 facts (That should automatically prove the silly question): 

1 - there are infinite numbers. 

2 - All numbers have the lowest factors as prime numbers. (Or all numbers are product of prime numbers and 1)

If there are only finite set of prime numbers, that would mean that the set of numbers is in fact finite, which is false.

Ex : Lets assume there are only 4 prime numbers i.e 2,3,5 and 7

The numbers 26, 91 wouldn't exist because 13 and 17 do not exist ... Get the logic ??

5. Is there a formula to check whether a number is prime or not ? 

 Ans : No

If there existed a formula, then scientists and maniacs wouldn't be using supercomputers to find new prime numbers everyday. They would simply use the formula to get new prime numbers. There would be no ATMs with ATM cards ... They exist .. so I can safely scream out that there is NO FORMULA.

I wrote this entry because I there is no good book or blog on mathematics without mentioning of prime numbers. Hope this blog becomes good now !!!! :-) (get the joke ??) :-P 

My new blog :- Dedicated to the beautiful world of Mathematics

I was in my first grade, when I encountered my first horrible experience with mathematics. I was a wonderful memorizer. I prefer to memorize rather than work it out logically, mainly because recalling is faster than creating logical stuff. Remember, how we are taught math tables for the first time ? Most of us prefer to learn it by heart and not understand things logically. Same applies to things like multiplication, division, differentiation, integration etc... But, not learn things logically can create hell lot of problems. 

When I was in my first grade I was trying to learn tables of 9 by heart. 

9 X 1 = 9

9 X 2 = 18

9 X 3 = 27

9 X 4 = 36

9 X 5 = 45

9 X 6 = 54

9 X 7 = 63

9 X 8 = 72

9 X 9 = 81

9 X 10 = 90

is the tables. I was told multiplication is in fact nothing but addition. So, tables of two were very easy. Just keep adding two everytime. 2 x 1 = 2. For 2 x 2 just add 2 to previous number and so on. Learning tables this way was easy till the tables of 6. 7 was difficult but surprisingly I could memorize them. 8 was more difficult but my brain had more space. 9 was the most difficult of them all. I remember spending days together trying to learn the table of 9 by heart. It was impossible. My mom used to ask me what was 9 * 6 ... I couldn't answer. She asked for 6 * 9 ... I could answer.... It was then that I was introduced to commutative law. She asked me to remember all tables till 8. For table of 9, all I had to do was just recall all the table's 9th element. 9 * 10 was easy because all i had to do was just write 9 and append 0. 

Now, I became a little better. But, as I had told you, 7 and 8 tables were pretty difficult for me. So, my mom told me another tricky method. She asked me to remember table of 9 till 5. i.e 

9 X 1 =  09 (She added zero purposefully)

9 X 2 = 18

9 X 3 = 27

9 X 4 = 36

9 X 5 = 45

Then for the rest .. all I had to do was just reverse the number in the reverse direction ... 

i.e 

9 X 5 = 45   - 9 X 6 = 54  (Observe that the numbers are reversed .... )

9 X 4 = 36  -  9 X 7 = 63

9 X 3 = 27  -  9 X 8 = 72 

9 X 2 = 18   - 9 X 9 = 81

9 X 1 = 09   - 9 X 10 = 90 

It took more than a week to see and learn these things. I was amazed by this.

WOW !!!!!!! Was it same for other tables too ??? I tried ... but failed ..  The tables of 9 instantly became my favorite. But, for the exam we were asked to learn only till tables of 8. ..... Murphy's law ??!!!!

As time passed, I still remembered my first encounter with table of 9. It was in my college that I actually learnt that this property of number reversal is actually due to a reason. 

Try to prove ::: if 9 | (10x  + y) then 9 | (10y + x) when x,y belong to set of integers. 

Prime numbers exist and their properties are so very important. They are used in infinitely many places. I could get the essence of the very famous P vs NP problem from these prime numbers. These prime numbers have made the heads of greatest brains in the world spin. 

I am reading a few scriptures on number theory and probability theory. The more I read , more I want to ... 

This blog is a dedication to the beautiful world of mathematics and a small device which was originally created to make life of mathematicians easier and has now more takers than the subject of mathematics (Computers)....