100 Prisoner Problems Mar 2024

Specific and General Solutions
Despite my lifelong interest in math, I had not heard of this problem until it was introduced by my 12-year-old grandson, Nicholas Lawley.

I start with the problem statement (excerpted from the Wikipedia).

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance.

A room contains a cupboard with 100 drawers. The director randomly puts one prisoner’s number in each closed drawer.

The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards.

If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die.

Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers.

What is the prisoners’ best strategy?

100 prisoners problem qtl1

Solution from the Wiki (spoiler alert)

The solution is provided in this wiki article about the 100 prisoners problem.

Link

The brilliant approach involves probability, integer partitions, and permutations of cycles within the integer partitions.

My Specific Solutions

After reading the wiki solution above, I wanted to work through the problem by hand, step-by-step. Of course, the 100-prisoner hand solution, with n = 100, would be long and tedious; therefore, I started with the 4-prisoner problem with n = 4 and I followed that with the 6-prisoner problem with n = 6.

See my calculation PDF here

Or here

The chance of success (all prisoners released), is as follows:

Referring to Page 5 of the PDF
For n = 4, the probability of success is \frac{24-14}{24} = \frac{5}{12} = 0.4167 = 41.67\%

Referring to Page 6 of the PDF
For n = 6, the probability of success is \frac{276}{720} = 0.3833 = 38.33\%


In summary

According to the wiki article, the solution for the general case of P prisoners is as follows:

The probability of success for the prisoners is 1 - (\italic{H}_{P} - \italic{H}_{P/2})

where \italic{H}_{P} is a harmonic number.

My calculations verify the solution shown in the wikipedia.

\mathit{H}_{k+1} = \mathit{H}_{k} + \frac{1}{k+1}, therefore:

\mathit{H}_{1} = 1

\mathit{H}_{2} = \mathit{H}_{1} + \frac{1}{2} = \frac{3}{2}

\mathit{H}_{3} = \mathit{H}_{2} + \frac{1}{3} = \frac{11}{6}

\mathit{H}_{4} = \mathit{H}_{3} + \frac{1}{4} = \frac{25}{12}

\mathit{H}_{5} = \mathit{H}_{4} + \frac{1}{5} = \frac{137}{60}

\mathit{H}_{6} = \mathit{H}_{5} + \frac{1}{6} = \frac{49}{20}

It follows that:

For P = 4: 1 - (\mathit{H}_4 - \mathit{H}_2) = 1 - (\frac{25}{12} - \frac{3}{2}) = \frac{5}{12} = 0.4167 checks ✓

For P = 6: 1 - (\mathit{H}_6 - \mathit{H}_3) = 1 - (\frac{49}{20} - \frac{11}{6}) = \frac{23}{60} = 0.3833 checks ✓


Reference and Related Interest

100 Prisoner Problems Mar 2024

Leave a Reply

Your email address will not be published. Required fields are marked *