↓Skip to main content
  1. Activities/
  2. Lecture Series/

Lecture Series 2025

Table of Contents

LS2501: Introduction to Combinatorial Game Theory #

Number of Talks: 3

Target

The subject of combinatorial game theory deals with two-player games of perfect information and no random devices. In this series of three talks, we will start by describing the winning strategies in several games including the game of nim. We would proceed by studying the rich mathematical structure of the games including their “simplest forms”, and prove the Sprague-Grundy theorem.

Schedule

  • Talk 1: Nim and Bouton’s Theorem

    • Speaker: Nikhil Nagaria (B. Math, 2025)
    • Abstract: Though the subject now has a great amount of deep theory, it once was a collection of nice puzzles, and one of the earliest results is Bouton’s theorem. Consider the simple game where there are a bunch of piles of coins. Two players are playing with a move being picking a pile and removing some (nonzero) number of coins. The person who removes the last coin wins. A simple example is two piles of 10 coins each. Then, the player who moves second can win no matter what the first player does, by imitating her moves and maintaining an equal number of coins. Then, the second player will never run out of moves, and win. Who has the winning strategy in a general setup? Bouton’s theorem tells us exactly that! And as it turns out, this solution can be applied to a far general class of games, which is the content of the celebrated Sprague-Grundy Theorem, which we will see in the next lecture of this talk series. We will also see solutions to two other games Kayles and Chomp, and develop some motivation for the general theory.
    • Date and Time: Saturday, 18th January 2025, 11:00 AM - 12:00 PM

  • Talk 2: The Sprague-Grundy Theorem

    • Speaker: Nikhil Nagaria (B. Math, 2025)
    • Abstract: We study games by assigning them values. These values can be the familiar integers, or something very different like an infinitesimal! We will see this natural recursive way to assign values, and learn how to formally define games as mathematical objects and see how to add and compare them. We will define what it means for a game to be impartial, and show the Sprague-Grundy Theorem which says that values of impartial games are precisely those of nim. In other words, studying nim values is enough to study this very large class of impartial games.
    • Date and Time: Saturday, 25th January 2025, 11:00 AM - 12:30 PM

  • Talk 3: Canonical Forms

    • Speaker: Nikhil Nagaria (B. Math, 2025)
    • Abstract: One game can be written in several equivalent forms and thus there is a natural question: among different forms of the same game, is there a natural simplest representative? Turns out, there are two kinds of reductions that can be repeatedly done to a given game. Thus, for any given game, one obtains a “simplest” form that cannot be reduced further. This is called the canonical form of the game, and we will see all of this formally in this talk. We will also give another proof of the Sprague-Grundy theorem using the theory of canonical forms.
    • Date and Time: Sunday, 26th January 2025, 11:00 AM - 12:00 PM

  • Venue: 2nd Floor Auditorium, Academic Building

  • Videos: [TBU].