Background
This project focuses on developing an interactive computer program related to a mathematical concept in group theory known as Keeler’s Theorem. It revolves around a science fiction narrative from the television series “Futurama” about a mind-swapping machine. When two people swap minds between a pair of bodies, they are only able to reach their own body again given that two extra people are added and have not had previous mind switches (Evans, et al., 2014).
Various mathematical concepts translated very well to the development of the program and can bridge the gap for novel applications in mathematics and computer science by offering a visualization of abstract topics using game theory.
Future Work
Pedagogy
Within a simple and transactional game are unique learning objectives related to mathematics and computer science that challenges students to utilize abstraction and sequential mapping to understand all possible paths under a given set of restrictions to reach a desired outcome.
Applications
- Completing interactive computer program, allowing the user to explore generalizations of the theorem
- Implementing educational feature that can explain relative facts in Keeler’s Theorem to the player and relate it to their specific plays for the game using tree graphs in extensive form
Game Theory
Defining a 2-player game:
From a given initial position, the player whose turn it is plays a move from the set of available positions. The players will alternate moves from remaining positions until a terminal position is reached and there are no more moves possible. The final position determines which player is the winner and loser (Ferguson, 2005).
Connection to mathematics:
- Objects in n positions, with a finite number of combinations available for game moves
- Initial and final position represent the identity permutation
- the number of given positions will determine whether new positions must be added to win the game
- Transpositions represent the legal moves available to players
- Permutations are the set of pairs for swapped minds and bodies
Diagram of Mind-Body Swap
The original pairing of mind and body is defined as the identity. Note that the starting position includes 4 minds, and the chosen moves are associated with the swapping of the denoted positions of minds. The resulting position is the updated placement of the minds in a set of bodies. Once all moves are player, the final position determines the winner of the game, given that the identity has been reached.
The final position reveals that the players were not able to pair the swapped minds to their original position, so neither player won the game. Reaching a final position does not guarantee that the player chose a path of moves resulting in the original position. This sample diagram emphasizes the impact that a strategic choice of limited moves has on the final position.
Theorem
The terms mentioned in the section of game theory translate to terminology within group theory such that minds, bodies, and their swappings can be represented by permutations and transpositions (Gallian, 2013).
- A group is a finite set of one-to-one functions closed under composition; there exists an identity, every element has an inverse, and pairs of elements can be combined without going outside the set.
- The symmetric group consists of all permutations within the set of n elements
- A permutation represents the total number of combinations available for n elements
- A transposition, or 2-cycle, is the exchange of two elements within a set of n elements
- The total number of 2-cycles in a symmetric group represent the relationship between elements, creating a cycle that results in either an even or odd permutation
- The permutation of transpositions represents the total number of non repeated swaps
- .An even permutation is defined as the product of an even number of 2-cycles, and conversely for an odd permutation with an odd number of 2-cycles.
- The alternating group consists of all even permutations in the set of n elements and comprises half of the permutations in the symmetric group.
These definitions contribute to the parameters set for the 2-player game such that legal moves and limitations of certain sets of n elements can be calculated. The set of legal combinations can then be populated for the players of the game while upholding foundations of Keeler’s theorem.
Conjectures
- For n mod 4 = 0 or 1, even permutations can have a winning sequence of moves.
- For n mod 4 = 2 or 3, odd permutations cannot reach the winning position without replacing missing elements using this fact:
- For each element c existing in the set of n elements that excludes the 2-cycle of ab, there exists the composition of 2-cycles ac, ab, and bc that can be inserted.
References
Evans, R, Huang, L., and Ngyuen, T. (2014). Keeler’s Theorem and products of distinct transpositions. American Mathematical Monthly 121, 136-144.
Ferguson, T. (2005). Game theory. University of California at Los Angeles, 1.
Gallian, J. A., (2013). Contemporary abstract algebra. Cengage Learning.
Acknowledgements
This research is supported by the Pacific Northwest Louis Stokes Alliance for Minority Participation (LSAMP) through the National Science Foundation under Award No. HRD-1410465
Research advisor: Dr. Marion Scheepers, Boise State University