Keeler’s Theorem and Products of Distinct Transpositions
2014; Taylor & Francis; Volume: 121; Issue: 2 Linguagem: Inglês
10.4169/amer.math.monthly.121.02.136
ISSN1930-0972
AutoresRon Evans, Lihua Huang, Tuan Huy Nguyen,
Tópico(s)Algorithms and Data Compression
ResumoAbstractAn episode of the television series Futurama features a two-body mind-switching machine, which will not work more than once on the same pair of bodies. After the Futurama community engages in a mind-switching spree, the question is asked, "Can the switching be undone so as to restore all minds to their original bodies?" Ken Keeler found an algorithm that undoes any mind-scrambling permutation with the aid of two "outsiders." We refine Keeler's result by providing a more efficient algorithm that uses the smallest possible number of switches. We also present best possible algorithms for undoing two natural sequences of switches, each sequence effecting a cyclic mind-scrambling permutation in the symmetric group Sn. Finally, we give necessary and sufficient conditions on m and n for the identity permutation to be expressible as a product of m distinct transpositions in Sn. Additional informationNotes on contributorsRon EvansRON EVANS received a B.S. from the University of Michigan in 1967 and a Ph.D. from the University of Illinois in 1974. After a two-year instructorship at the University ofWisconsin, he joined the UCSD Mathematics Department in 1975. His recent work focuses on character sum evaluations, with connections to Hecke eigenfunctions. He is coauthor of Gauss and Jacobi Sums (Wiley, 1998) with his Ph.D. advisor Bruce C. Berndt and Kenneth S. Williams. His hobbies include playing the violin, bicycling, and losing to the computer at chess.Lihua HuangLIHUA HUANG obtained her B.S. in mathematics from the University of California at San Diego in 2012. Her research interests include group theory and several complex variables. She has given presentations on her three research projects at conferences held by Ohio State, Cal Poly Pomona, Penn State, UCSD, and the 2013 Joint Mathematics Meetings in San Diego. She received a GAANN Fellowship at Rutgers University, where she is a second year Ph.D. student in mathematics. Her hobbies include ping-pong, racquetball, and cooking.Tuan NguyenTUAN NGUYEN graduated from UCSD in 2012 with a B.S. in applied mathematics. He is currently pursuing a master's degree in statistics at Stanford University with specialization in machine learning, data mining, natural language processing and information retrieval. His hobbies include soccer and tennis.
Referência(s)