# Combinatorial Games, Redistricting Game, and Graph Music

Welcome to this week’s Math Munch!

Have you ever played tic-tac-toe? If so, maybe you’ve noticed that unless you or your opponent makes a bad move, the game always ends in a tie! (Oops– spoiler alert!) Why is that? And what makes tic-tac-toe different from other games that have unpredictable outcomes, like Monopoly or the card game War?

Tic-tac-toe is similar to other kinds of game that mathematicians call combinatorial games— or games where there is no chance involved in the outcome and neither player has information that the other one doesn’t. This means that depending on who starts, where they go, and where each player decides to go next, the outcome is completely predictable and everyone playing could know what it is before it even happens. No surprises!

Now, this might also sound like NO FUN to you (why play the game at all if everyone knows what’s going to happen?) but I think it introduces a new kind of fun– figuring out what the outcomes could be! One of my favorite combinatorial games is the game NIM.

Here’s an example of a starting NIM board. If you go first, can you win? (Assuming your opponent never makes a mistake.)

NIM is a two-player game. You start with several piles or rows of objects (here they’re matches). On each turn, a player removes some objects from a pile– any number they want. BUT the player who’s forced to remove the last match loses!

There’s no chance in NIM– no dice determining how many matches you can remove, for example. Also both players know the rules and how many matches are in the piles at all times. That means that if you thought about it for a while, you could figure out who should win or lose any game of NIM. Maybe playing the game NIM isn’t super fun– but thinking about it like a puzzle is!

More versions of online NIM can be found here and here. And to read about combinatorial games we’ve written about in the past, check out this interview with mathematician Elwyn Berlekamp!

Next up, it’s presidential election time here again in the U.S.! Did you know that there’s a lot of mathematics behind what makes elections work? Four years ago, before the last presidential election, we shared a great series of YouTube videos about the math of elections.

A map in the redistricting game.

A big way that math gets involved in elections is through how politicians decide to draw districts, or regions of states that get to elect their own representative to the House of Representatives and elector to the Electoral College. The math behind drawing districts ranges from simple arithmetic to graph theory, or the field of math that deals with how parts of a shape or diagram are connected. To learn more about drawing election districts and the math behind it, check out the Re-Districting Game! In this game, you play the part of a map maker who works with the Congress, governor of your state, and courts to make a district map that meets everyone’s needs.

Finally, I recently ran across a series of graph music videos! What’s that? Videos in which a graph (made on Desmos) dances along to music, much like people would in a regular music video. Here’s one of my favorites:

The equations on the left-hand side of the screen create the images you see and the rhythm of the animation. Want to make your own graph music video? Share it with us!

Bon appetit!