Buses, Bullies, and Bijections

Year of Award: 2017

Award: Allendoerfer

Publication Information: Mathematics Magazine, vol. 89, no. 3, June 2016, pp. 167-176.

Summary: (adapted from the MAA Prizes and Awards booklet for MAA MathFest 2017) Suppose n people are assigned to n seats on a bus such that person i is assigned to seat i, for 1≤i≤n. Persons 2 through n enter the bus and take seats randomly. When person 1 (A) enters, A sits in his or her assigned seat if it is available, otherwise A forces the person in his or her seat to move and A requires the displaced person to take his or her assigned seat, possibly forcing someone else to move. This process continues until there are no more displaced persons. The authors ask: What is the probability that person 2 will have to move? This simple question starts the reader on a journey through the world of bijections on the symmetric group S_n.

Read the Article

About the Authors: (From the MAA MathFest 2017 MAA Prizes and Awards Booklet)

Vladimir Pozdnyakov received his Ph.D. in statistics in 2001 from the University of Pennsylvania. Since that time he has taught at the University of Connecticut, where he is currently professor of statistics. His research is mostly in applied probability, and he has a particular interest in the discovery and exploitation of martingale tricks.

J. Michael Steele received his Ph.D. in mathematics from Stanford University in 1975. He has taught at U.B.C., Stanford, CMU, Princeton, and the Wharton School of the University of Pennsylvania. He has worked in many parts of probability theory, and he is the author of several books including The Cauchy-Schwarz Master Class published by the MAA.