The Mensa Correctional Institute

Abstract

We investigate the following puzzle and several variations, some of which have quite surprising answers. Alice and Bob are in prison under the care of warden Charlie. Alice will be brought into Charlie’s office and shown 52 cards, face-up in a row in an arbitrary order. Alice can interchange two cards. Charlie then turns all cards face-down in their places and Alice leaves the room. Then Bob is brought in and Charlie calls out a random target card. Bob can turn over cards, one after another, at most 26 times as he searches for the target. Both prisoners are freed if Bob finds the target. Find a strategy that never fails.

MSC:

• Primary 91A28
• Secondary 05A15; 05D99

Acknowledgments

We thank Mark Rickert for his enthusiasm in helping with some of the computer searches, Richard Stong for sharing his expertise in the probabilistic study of permutations, and Veit Elser for discovering the name of the prison.

Additional information

Notes on contributors

Larry Carter

LARRY CARTER was a professor in the Computer Science and Engineering department at the University of California at San Diego, where his research interests included high-performance computing and computer architecture. Before UCSD, he was a Research Staff Member at IBM’s Watson Research Center. In retirement, Larry enjoys having time for cooking, biking, music, and recreational mathematics.

Stan Wagon

STAN WAGON is recently retired from Macalester College. His main interest is in using the power of modern software to visualize abstract mathematical concepts. His latest book is a second edition, with G. Tomkowicz, of The Banach–Tarski Paradox. Other interests include ski mountaineering, climbing, mushroom hunting, and playing the piano. He is one of the founding editors of Ultrarunning magazine, but now finds that covering long distances is much easier on skis than in running shoes.