Locks and keys: How fast can you open several locks with too many keys?
This is an incremental educational problem aimed at introducing undergraduate students to research, with no direct practical application.
The paper tackles the problem of determining the average number of trials needed to open n locks using N keys, where N is at least n, by studying and comparing three different strategies. It provides theoretical results and implementations as illustrations.
This short note is the result of a French "Hippocampe internship" that aims at introducing the world of research to young undergraduate French students. The problem studied is the following: imagine yourself locked in a cage barred with $n$ different locks. You are given a keyring with $N \geq n$ keys containing the $n$ keys that open the locks. In average, how many trials are required to open all locks and get out? The article studies $3$ different strategies and compare them. Implementation of the strategies are also proposed as illustrations of the theoretical results.