Mathematics and Computers

Reading topics - April 1, 2024

Recent articles on computers for math

An issue of the Bulletin of the American Mathematical Society focuses on the use of computers in math.

Follow the links or findthe articles in the cloud.

100 prisoners problem

The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem, 100 numbered prisoners must find their own numbers in one of 100 drawers in order to survive. The rules state that each prisoner may open only 50 drawers and cannot communicate with other prisoners. At first glance, the situation appears hopeless, but a clever strategy offers the prisoners a realistic chance of survival. See the youtube video.

Danish computer scientist Peter Bro Miltersen first proposed the problem in 2003.

Source: Article and Preprint.

Problem description. “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?”