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