locker_simulation


locker_simulation, an Octave code which simulates the locker problem, in which gym users have left their wallets in lockers; someone has scrambled all the lockers, and the gym users need a strategy that maximizes the chance that everyone will find their wallet by searching a limited number of lockers.

This puzzle is often given assuming there are 100 gym users and 100 lockers, and each user is allowed to examine no more than 50 lockers.

It might seem that there is no winning strategy. Indeed, a single user opening lockers are random has a reasonable chance of finding their wallet, which you might estimate at roughly a 50% chance.

However, the puzzle asks a more challenging question:

Is there a strategy that makes it likely that all 100 users will find their wallets?
Now it would seem that if each user does a random search, the likelyhood that they will all succeed will be something like (1/2)^100, essentially a hopeless case.

Surprisingly, assuming that the wallet scrambling was really done at random, it turns out that there is at least one strategy that offers a roughly 31% chance that all 100 users will find their wallets.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

locker_simulation is available in a MATLAB version and an Octave version and a Python version.

Related Data and codes:

locker_simulation_test

octave_simulation, an Octave code which uses simulation to study card games, contests, and other processes which have a random element. Usually, the purpose is to try to predict the average behavior of the system over many trials.

Reference:

  1. Nick Berry,
    100 Prisoners Escape Puzzle,
    https://datagenetics.com/blog/december42014/index.html
    Posted December 2014.
  2. Pradeep Mutalik,
    Help Star Trek's Lieutenant Uhura Overcome Astronomical Odds,
    Quanta Magazine, 18 August 2022,
    https://www.quantamagazine.org/help-star-treks-lieutenant-uhura-in-this-probability-puzzle-20220818/
  3. Wikipedia,
    100 Prisoners Problem,
    https://en.wikipedia.org/wiki/100_prisoners_problem
  4. Peter Winkler,
    Seven puzzles you think you must not have heard correctly,
    https://math.dartmouth.edu/~pw/solutions.pdf

Source Code:


Last revised on 18 December 2022.