27 January 2010

A totally nontrivial prisoners problem

(I promised the guys in a Nadder! to post this, so here I go! Keeping my promise!)

Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:

There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.

The question is: Can the prisoners devise a strategy to increase their chance of survival?

To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2100 = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.

But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.

After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.



Away for 6 months

As of 2 weeks ago, I'm spending my time here:

Blogging is not my top priority, so I'll do it when convenient. The problem is that there are so many issues I'd like to talk about, but so little time...

Religious scientists

I asked, several times, in various forums, for an explanation of the fact that there are many scientists who are religious. One answer is that our milieu affects some more than others. So, some people, no matter how rational they may be in their field, cannot escape the prison they were thrown into at some point of their lives. Another answer lies in the meaning of the word "scientist".

Be it as it may, what we cannot infer from the fact that there are religious scientists is that religion and science are compatible. The mere fact that the intersection of the two sets is nonempty does not imply much.

Too many words for a simple idea, best explained here:

26 January 2010

Holy water causes acute intestinal pain

This is the photo of a Russian religious idiot who drunk "holy" water to celebrate Epiphany on 19 January 2010. And then he had to go to the hospital.

Actually, more than 100 believers (i.e. idiots) thought that drinking "holy" water is the right thing to do during the religious feast of Epiphany. And they all had to go to the hospital to be treated for acute intestinal pain.

N.B. The Russian Orthodox Church celebrates the Epiphany on 19 January, 13 days later than other churches, because they are stuck with the Julian calendar. When the Bolsheviks finally switched to the Gregorian calendar in 1918, the Russian church did not follow this. I guess they didn't want to do the same thing as the "atheists".

6 January 2010

Cooking lessons from the Swedish chef

Excellent recipes, his songs are a bit repetitive though.

Turtle soup


Chocolate mousse

Banana split

Hot sauce

Christmas dinner

5 January 2010


Unprecedented bad weather for long time now in Scotland and the whole UK. When I woke up today it was -9 C outside. It's warmer now, snowing heavily. We expect temperatures around -20 C in the weekend in certain parts of Scotland. It is said it's the coldest winter in 100 years. (Yes, it's colder in Novosibirsk, around -40 C, but it's normal there.)

2 January 2010

Irish atheists challenge blasphemy law

A new law in Ireland, which came into force on 1 January 2010, makes blasphemy a crime and punishable by a fine of up to 25,000 euros (£22,000; $35,000). The Irish government says it is needed because the republic's 1937 constitution only gives Christians legal protection of their beliefs.

The group "Atheist Ireland" responded by publishing 25 quotes it considers anti-religious on its website. There are quotes by Muhammed, Jesus, Pope Razinger, Dawkins, and the Irish Minister for Justice, among others. Atheist Ireland said its aim is to have the law repealed and to attain a secular Irish constitution. The group will fight any action taken against it in court.

The law is, indeed, anachronistic and stupid. Whereas it is absurd, according to the 1937 law, to only give Christians protection of their beliefs, the response should not have been to give legal protection to all religious beliefs but to abolish protection of beliefs altogether, to decriminalize blasphemy.

Evolution in lifeless proteins

Very intereresting!

Scientists have shown for the first time that "lifeless" prion proteins, devoid of all genetic material, can evolve just like higher forms of life. In other words, they are subject to mutation and natural selection.


What measure theory is about

It's about counting, but when things get too large.
Put otherwise, it's about addition of positive numbers, but when these numbers are far too many.

The principle of dynamic programming

max_{x,y} [f(x) + g(x,y)] = max_x [f(x) + max_y g(x,y)]

The bottom line

Nuestras horas son minutos cuando esperamos saber y siglos cuando sabemos lo que se puede aprender.
(Our hours are minutes when we wait to learn and centuries when we know what is to be learnt.) --António Machado

Αγεωμέτρητος μηδείς εισίτω.
(Those who do not know geometry may not enter.) --Plato

Sapere Aude! Habe Muth, dich deines eigenen Verstandes zu bedienen!
(Dare to know! Have courage to use your own reason!) --Kant