Computer Science 5th Years Master's Thesis Presentation
— 4:30pm
Location:
In Person
-
Traffic21 Classroom, Gates Hillman 6501
Speaker:
MIRABEL HU
,
Masters Student, Computer Science Department, Carnegie Mellon University
Exploring Variations of Wythoff Nim
We investigate two modifications to the traditional rules of Wythoff Nim, a combinatorial game. In Wythoff Nim, players take turns removing stones from a pair of piles. In each turn, a player chooses to either (1) take any number of stones from one pile or (2) take an equal number from both. The player removing the last stone wins. A seminal result of Wythoff states that at any point in the game, the current player is in a P-position — that is, guaranteed to lose assuming the other player plays optimally — if and only if the pair of pile sizes is of the form (nø, nø^2) for some natural number n, where ø = 1.618… represents the golden ratio.
This thesis introduces a variant of Wythoff Nim, which we call W(a,b), characterized by positive integers a and b, where players' moves are constrained to either removing a multiple of a from the first pile, a multiple of b from the second, or an equal number from both. We prove that the P-positions of this variant also follow sloping “beams”, but with slopes determined by a and b.
Thesis Committee:
Danny Sleator (Advisor)
Klaus Sutner