Math + Making

A student blog for Math 189AH: Making Mathematics at Harvey Mudd College

The 100 Prisoners Problem

Kaeshav Danesh

For this project, I wanted to design an interactive version of the 100 prisoners problem.

The Problem

The problem starts with 100 boxes labeled 1-100 and 100 pieces of paper labeled 1-100. The papers are distributed randomly into the boxes. Now, there are 100 prisoners labeled 1-100. They are told that if all 100 of them are able to draw the paper with their number given 50 chances, then they can all leave. However, the catch is that they cannot communicate with each other after opening their box. But, they can devise a strategy before hand. What is the optimal strategy?

When trying to solve this problem, a lot of people will try to make this about communicating information somehow. But, the optimal strategy requires you to think about this problem as a permutation problem. I will not spoil the solution in this post, but there are more resources on this problem in the references at the bottom of the page.

The Project

To make the boxes for this problem, I cut out rectangular strips of paper and folded them. Then, I glued down the sides. Then, you could put little slips of paper inside the fold.

The folded pieces of paper and the smaller slips are all labeled. I made 15 of these in the end.

The Math

I think this riddle is a good way to learn about problem solving. Often times when faced with mathematical challenges, it is good to think of the problem in different ways. So instead of seeing the 100 prisoners problem as a way of creating a secret code to communicate, you see it as a problem involving the permutation of numbers.
I also think that the intuition behind this problem is used a lot in abstract algebra. Often times when studying groups, it is useful to see how the group elements permute. In fact, there is a theorem called Cayley’s Theorem that states every group is isomorphic to a subgroup of the symmetric group, which describes all the permutations of the group elements.

Refrences: <- video explaning solution <- wikipedia article with solution’s_theorem


Leave a Reply

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