On Unexpected Hanging Paradox and applications in law enforcement

[Note: this post has nothing to do with the ongoing executions in Iran.]

Unexpected hanging paradox is a well-known alleged logical paradox about a prisoner's response to an unusual death sentence. To quote Wikipedia, here is the statement of the paradox:

A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day. Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the "surprise hanging" can't be on a Friday, as if he hasn't been hanged by Thursday, there is only one day left - and so it won't be a surprise if he's hanged on a Friday. Since the judge's sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday. He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn't been hanged by Wednesday night, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all. The next week, the executioner knocks on the prisoner's door at noon on Wednesday — which, despite all the above, will still be an utter surprise to him. Everything the judge said has come true.

This has intrigued me again and again and I could never come to peace with it. While researching this recently I came across this paper which is a non-exhaustive survey of various tries to model the paradox. Great read.

Today I came across a blog post by Ed Felten called Targeted Copyright Enforcement: Deterring Many Users with a Few Lawsuits. While I find it very disturbing that a scientist like Ed Felten may be helping RIAA better screw people by their copyvio lawsuits, the puzzle and the solution provided are well worth a read. Not irrelevant to the Hanging Paradox, though in this case the reasoning may actually work.

Labels: copyfight, puzzle

¶ 5:14 PM   0 comments

 Ultimate Shell Puzzle

Dave: I found the answer to that puzzle the hard way a few years ago. The way I found it though makes a much more interesting puzzle:

What does the following script do:

#!/usr/bin/env PATH=/bin:/usr/bin python
print "Hello"

Labels: Dave, puzzle, shell

¶ 4:27 AM   5 comments

 Linux Shell Puzzle

Write a shell script named pchdir that when run like pchdir /bin it will change the current directory of its parrent process to /bin.

Labels: linux, puzzle, shell

¶ 1:56 AM   4 comments

 PUZZLE SOLUTION: Group Strategy

This is the solution to the puzzle Group Strategy that I posted a few weeks ago. Make sure you give it a try before reading further.

Intro:

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

Strategy:

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

Proof:

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

Update:

Proof that the bound is tight: While failure probability is not more than ln(2k) - ln(k), using the same idea, it's not less than ln(2k+1) - ln(k+1). So, success probability is between 1 - ln(2) and 1 - ln(2 - 1/(k+1)).

Labels: puzzle, solution

¶ 4:13 PM   2 comments

 PUZZLE: Group Strategy

Coming back from Montreal yesterday, Peyman told me the following puzzle which is probably the coolest of its kind I've ever heard. Quite the like that you try hard proving to be wrong first. Anyway:

(I first tried to write it down as prisoners and all, but gave up. Here it goes bare:)
There are 2k men numbered 1 to 2k. And a room with 2k boxes inside (also numbered 1 to 2k), and each man's number is written on a paper and placed in one of the boxes, such that every box has a number in it and the distribution is uniform.

Now there is a game (trial, whatever): each man goes into the room, opens and sees the number inside k of the boxes of his choice, and comes out, altering nothing in the room, and not communicating with anyone during the experience. Before the game starts the men have a chance to develop a strategy, but other than that they can't communicate at all. Anyway, after everyone has visited the room, if all of the men can tell in which box their number is placed, they win, otherwise they lose.

Show that the men can develop a strategy with a expected winning probability that is not less than a positive constant regardless of k.

Labels: puzzle

¶ 7:46 PM   12 comments