At first I must say that I have no gift in English, or Russian. So if you can’t catch my meaning, but what I can say is sorry. I promise I will try my best to improve my English. And I still have interest in Russian, for the reason that my dad is a great Russian speaker. Maybe I can communicate with you in Russian soon after.
Ok, let’s go! What I want to talk about is an interesting problem, Game Theory. Yes, I will connect Game Theory with ACM, and show you how to deal with these problems.
But what is Game Theory? I quote the explanation in wiki.
Game theory attempts to mathematically capture behavior in strategic situations , in which an individual's success in making choices depends on the choices of others. http://en.wikipedia.org/wiki/Game_theory
So it seems used in economics mostly. There’re many famous economists mastering it, such as Nash. But compared with the complex economics, I prefer to the games which kids love. Now I will tell you some stories about Game Theory.
One day, the Avatar comes to the island and told to them three: “Now I give you a chance to enter the Heaven, Pandora. I had dyed your hair red or black. Each of you can only see the other two’s hair color, but never see your own color, and no one will tell you what’s your color is. When you know your color, please face to the sun and kill yourself at dusk, and then I will take you to the Heaven. Good luck! Bye!”
The three poor men looked at each other, and they don’t know what to do, only to wait. The life returns to normal. They lived in harmony for several years. But in one morning, a stranger invaded the island and broke the peace.
The stranger noticed everything about the three. Soon he left the island and left one sentence: At least one of you three has red hair.
They looked at each other again, and went back to their own caves, dropped into reveries.
In the second morning, they got together in the centre of the island, looked at each other, and returned.
But in the dusk of this day, something happened. Two of the three killed themselves successfully, and went to the world of Pandora!
In the third morning, the last one went to the centre of the island, of course he saw no others, and he also had a success suicide in the dusk.
So, what happened to them? How could they do it? I feel puzzled!
Thank you for reading it, and I think you can solve the problem. I’ll give the analysis in next blog, it will come soon!
This is a famous kind of logic called epistemic logic that is usually used to explain similar situations. The solution is two of the inhabitants have red hair and the other black one.
Let us start considering a simpler version of the puzzle where we have two inhabitants: A and B. If A and B has different color (one red and the other black), then each of them in the first day after the avatar leaves will know the color of their hair and kill themselves. Let us assume that they both have red hair, then they will know the color in the second day. The reason for this is that they will figure out that if they had different colors, each would have killed himself in the previous day.
Let us apply the same reasoning for n=3. If only one inhabitant has red hair, he would know in the first day and he would have killed himself (call it case 1).
Let us assume that we have at least two inhabitants with red hair. If we have two with red hair and one with black, then those with red hair can see one person with red hair and other with black but they cannot see theirs. So they will not kill themselves in the first day. In the second day, they will know that the color of their hair is red as otherwise we would have had case 1. Both redheads will kill themselves and the inhabitant with black hair will know his hair color in the third day and kill himself.
This puzzle is formally known as the muddy children puzzle where we have n inhabitants.