Game Night at the Binomial Elks Club

Question

The Binomial Elks Club, being predominantly composed of ambitious and competitive personalities, often held game nights in which members enjoyed battling each other for high stakes and bragging rights. On this particular night, a crowd had gathered around Matt Damon and Ben Affleck. These two friends were engaged in a tense game of intellect, played on a small game board. The rules of this game were:

1. There is a 3x3 game board that initially starts with a token in each space.
2. Players alternate taking turns. A player's turn consists of taking one or more tokens from a single row or column of the board. The tokens taken are removed from the board. The tokens do not need to be contiguous, just from the same row or column.
3. The player who takes the last token wins.
4. Each player wagers \$1 million. The winner takes all, the loser gets nothing.
5. The order of play is decided by a coin flip. The winner of the coin flip decides whether they will play first or second.

Matt Damon won the coin flip and eventually won the game. Did he choose to play first or second, and what was his strategy?

---

Having just lost $1 million, Ben wanted to go double or nothing in a rematch. But before Matt could accept, Elon Musk challenged both of them to a 3-person variant of the same game. The rules were slightly different:

1. The game board and moves are the same as the previous version. The three players take turns in round robin order, i.e. 1, 2, 3, 1, 2, 3, etc.
2. The winner is the player who takes the last token. The player whose turn comes after the winner is 2nd place.
3. Each player wagers \$1 million. The winner gets \$2 million, the 2nd place player gets \$1 million, and the 3rd place player gets nothing.
4. The order of play is decided by drawing straws. The long straw gets to pick whether to play first, second, or third. The middle straw gets to pick between the two remaining positions. The short straw is stuck playing in whatever position is left.

Ben picked the long straw and Matt picked the middle straw. Which positions did Ben and Matt choose to play, what were their strategies, and how much did each win?

---

Elon Musk was steaming after losing the previous game. He demanded that the three play a double or nothing match. Matt offered to raise the stakes to \$10 million. Elon agreed on the condition that the straw orders should be reversed from the last game, i.e. Elon picks first then Matt picks second. Matt and Ben gave each other a knowing look and agreed.

Even though Elon chose the same position and played the same strategy as the winner of the previous match, he ended up losing. What happened?

---

Optional bonus question: Suppose the game board were 4x4 instead of 3x3. How would the answers change for the first two games played? Since the 4x4 strategy can get quite complex, it would be enough to say which position to pick and what the first move(s) should be, rather than list a full tree of possibilities.

_{This is my contribution towards Generalist Countdown — game}

Answer 1

Any permutation of the rows and columns is treated as an "equivalent" board.

Part 1: Matt chooses to go second.

(Case A) If Ben takes 2 or 3 tokens, then Matt can turn it into a 2x2 board and win.

(Case B) If Ben takes 1 token: $$\begin{array}{ccc} O & O & O \\ O & O & O \\ \_ & O & O \end{array}$$ then Matt can take 2 tokens to make the board look like:

$$\begin{array}{ccc} \_ & \_ & O \\ O & O & O \\ \_ & O & O \end{array}$$ No matter what Ben does, Matt can either turn it into a 2x2 board or: $$\begin{array}{cc} O & \_ \\ \_ & O \end{array}$$

Part 2: You never want to let the player ahead of you win (if they win, you lose).

On a board with three tokens, if you can take all of them you win, otherwise you take one piece in such a way to get second. (The player before you wins.)

All four and five token boards can in one move become a three token board (where not all tokens are in the same row/column). Therefore, all four and five token boards are winning!

If the first player takes 2 tokens: $$\begin{array}{ccc} O & O & O \\ \_ & O & O \\ \_ & O & O \end{array}$$ Then the second player must only take the one remaining piece in that row/column (or otherwise lose by letting the third player win). $$\begin{array}{ccc} \_ & O & O \\ \_ & O & O \\ \_ & O & O \end{array}$$ The first person automatically wins!

Ben chooses to go first, and Matt chooses to go second.

Part 3: I concluded the player going first always wins this three-player game on a 3x3 board. Ben and Matt must not have played a subgame perfect strategy for Elon to lose again. Perhaps they colluded? Then, Ben and Matt are acting as a team whose goal is to make Elon lose.

Suppose in Part 2, Ben only took 1 token to start, and Matt took 2 tokens. In Part 3, Elon copies Ben's strategy. That is, Elon starts and takes 1 token. But now, Ben and Matt each take one token. Elon then starts on a 2x3 board and automatically loses.

Optional bonus question:

Part 1b: I am not sure. I'd conjecture that in a nxn board it is winning to go first only if n is even.

Part 2b: Choose Elon to go last. Ben and Matt can then make Elon start with the following board:

$$\begin{array}{cccc} O & \_ & \_ & \_ \\ \_ & O & O & O \\ \_ & O & O & O \\ \_ & O & O & O \end{array}$$

Unless Elon takes 3 tokens, then they can turn into a 2x3 board for Elon's next turn. If Elon takes 3 tokens, then they can turn it into:

$$\begin{array}{cc} O & \_ \\ \_ & O \end{array}$$

Part 3b: Elon copies Ben and goes first, but instead they leave him with a 2x3 board.