Talk: Impartial games for generating groups

April 30, 2013 — 4 Comments

On April 23, 2013, I gave two talks at the University of Nebraska at Omaha. The first talk was part of the Cool Math Talk Series and was titled “Impartial games for generating groups.” Here is the abstract.

Loosely speaking, a group is a set together with an associative binary operation that satisfies a few modest conditions: the “product” of any two elements from the set is an element of the set (closure), there exists a “do nothing” element (identity), and for every element in the set, there exists another element in the set that “undoes” the original (inverses). Let $G$ be a finite group. Given a single element from $G$, we can create new elements of the group by raising the element to various powers. Given two elements, we have even more options for creating new elements by combining powers of the two elements. Since $G$ is finite, some finite number of elements will “generate” all of $G$. In the game DO GENERATE, two players alternately select elements from $G$. At each stage, a group is generated by the previously selected elements. The winner is the player that generates all of $G$. There is an alternate version of the game called DO NOT GENERATE in which the loser is the player that generates all of $G$. In this talk, we will explore both games and discuss winning strategies. Time permitting, we may also relay some current research related to both games.

The content of the talk falls into the category of combinatorial game theory, which is a topic that is fairly new to me. The idea of the talk is inspired by a research project that I recently started working on with Nandor Sieben who is a colleague of mine at NAU. In particular, Nandor are working on computing the nimbers for GENERATE and DO NOT GENERATE for various families of groups. If all goes according to plan, we’ll have all the details sorted out and a paper written by the end of the summer.

After a brief introduction to combinatorial game theory and impartial games, I discussed both normal and misère play for three impartial games: Nim, X-Only Tic-Tac-Toe, and GENERATE. You might think that X-Only Tic-Tac-Toe is rather boring, but the misère version, called Notakto (clever name, right?) is really interesting. In fact, there is a free iPad game that you can download if you want to try it out. Also, if you want to know more about the mathematics behind Notakto, check out The Secrets of Notakto: Winning at X-only Tic-Tac-Toe by Thane Plambeck and Greg Whitehead.

Here are the slides for my talk.

Immediately after giving the Cool Math Talk, I facilitated a 2-hour Math Teachers’ Circle as part of the Omaha Area MTC. The audience for the MTC mostly consisted of middle and high school mathematics teachers. The theme for the circle was the same as the Cool Math Talk, but instead of me talking the whole time, the teachers played the games and attempted to develop winning strategies.

This was my second time running a MTC at UNO. In February of 2012, I ran a circle whose general topic was permutation puzzles. You can find the slides from last year’s circle here.

Both talks were a lot of fun (especially the MTC). Thanks to Angie Hodge for inviting me out to give the talks.

Dana Ernst

Posts Twitter

Father of two boys, husband, mathematician, cyclist, trail runner, rock climber, and coffee drinker. Columnist for MAA blog Math Ed Matters.
  • Simon H

    Ummmm, ties are possible in chess. Positions where all pieces are gone and only the kings remain are pure ties.

    • Simon, you’re right about the ambiguity with chess. In fact, I removed ordinary Tic-Tac-Toe because of the tie issue. In general, the literature about combinatorial game theory is inconsistent about ties. In some cases, there is an explicit requirement that there is a winner in a finite number of moves. This would ban games like chess and ordinary Tic-Tac-Toe. On the other hand, it is common to see these types of games listed as examples of combinatorial game theory. I should have been more consistent about the stance that I was taking. Thanks for having a look at the slides. Perhaps I’ll modify them in light of your comment.

      • Simon H

        Fair enough, yes it is quite a common example in game theory books. Anyway, thanks for sharing the talk I found it interesting.

  • Simon H

    I’d go so far as to say this is pretty cool, read it in a hurry yesterday because I was busy at work.