Thursday, March 29, 2007

Prisoner Problems

Quite a few well-known logic puzzles involve a prison setting, giving them a darker tone that makes them memorable and more fun to think about.

This joke prisoner problem is amusing but impossible, as its rather surreal solution involves English homonyms.

I also won't bother describing the famous prisoner's dilemma from game theory.

Then there's the paradox about the prisoner who's told he'll be executed some time next week and that it will be a surprise. So he reasons thus: "They can't kill me on Friday, because I would know by Thursday night and it would not be a surprise."

"But this implies if they haven't killed me by Wednesday night, then I know I'm dead on Thursday because I can't be killed on Friday. Which means it wouldn't be a surprise. Hence I cannot be executed on Thursday."

"Repeating this argument a few times shows that I cannot be executed on any day next week!" he concludes triumphantly.

But on Tuesday morning he is executed, much to his surprise! What's going on?

And there's the tale about the prisoner who is to choose his method of execution: if the last statement he utters is true then he is executed in some gruesome fashion, and on the other hand, if it is false then he is executed in some different but equally gruesome fashion. (The particular methods of execution change from telling to telling. I just can't think of any right now.) What should he say?

A tougher puzzle involves one-hundred prisoners in a prison that contains one-hundred cells and a single room with a single light bulb that can be turned on or off. Every day a prisoner is chosen at random and placed in the room. At any time, any prisoner can ask for freedom. When he asks, if every prisoner has spent at least one day in the room with the light bulb then everybody is set free. (The warden has been keeping track.) Otherwise everybody is executed.

The prisoners can talk amongst themselves before entering this bizarre jail, but once inside they are kept isolated, and the light bulb becomes their only means of communication. How can they free themselves?

Lastly, there is a similar problem that is the main reason for this post. A friend told me this puzzle a few months ago and I don't want to forget it.

Again, there are one-hundred prisoners and a special room, but this time the room contains one-hundred identical boxes, each containing exactly one slip of paper bearing a prisoner's name. Every prisoner's name is present, but no one knows which box contains which name.

The prisoners are taken to the room one at a time. Once inside they are allowed to open and examine the contents of up to fifty boxes. They must then leave the room as they found it, so the boxes they chose are closed when they are done.

After all prisoners have visited the room, if each prisoner has seen his name on a slip of paper then they are all free to go. Otherwise they are all executed.

As before, they can all examine the room and boxes (but not open them) and devise a strategy together beforehand, but no communication is permitted once the process begins.

Clearly if a prisoner picks fifty boxes at random he has only a 50% chance of finding his own name, and if every prisoner does this then the chance that all of them find their names is 1/2^100. That is, they will almost certainly be executed.

How can they obtain at least a 30% chance of surviving?

Wednesday, March 7, 2007

Shiny Colourful Buttons

Here's a trick I've seen mentioned in other geeky blogs that deserves to be more well-known and widespread: only have page icons (favicons) on the Firefox bookmarks toolbar. Simply delete the names in bookmark properties. Or try the Smart Bookmarks Bar extension. Note separators can be inserted to help organize the icons.

Not only is it stylish, but it frees up precious toolbar real estate for more bookmarks. Also I find myself drawn to the pretty little pictures. I visit those enticing links more often nowadays.

One might worry about forgetting which icon does what, but presumably the links on one's toolbar are frequently used, making this unlikely. Anyway, to find out where they go, just click on them! (i.e. the standard action following the thought: "I wonder what this button does...")

The sole drawback is that some webpages don't have icons, or have one that looks identical to another, or looks horrible. To solve this, use the Favicon Picker 2 extension to assign a good icon to that bookmark.

A related idea is to hide text on certain tabs, which can be achieved using the FaviconizeTab extension.

By the way, googling for "favicon picker" finds many of the aforementioned blog posts [1, 2, 3, 4, 5], some containing great screenshots. Not everyone is enthralled by the idea however, and some even want the opposite.