Two-Player Games

  1. 1982 Leningrad Mathematics Olympiad

    Anna and Boris play a game with a stack of 100 counters. Anna goes first, and moves alternate thereafter. In each move, a player divides a stack of at least two counters into two smaller piles. The loser is the player without a move, when each stack consists of exactly one counter. Prove that Anna must win this game.

  2. 1987 Leningrad Mathematics Olympiad

    Anna and Boris play a game on a 9 × 9 chessboard. Anna goes first and turns alternate thereafter. In each move, Anna puts a red counter on a vacant square while Boris puts a blue counter on a vacant square. When the board is completely filled, a row with more red counters than blue counters is called a red row, and a blue row otherwise. Red and blue columns are similarly defined. The score for Anna is the sum of the numbers of red rows and red columns while that for Boris is the sum of the numbers of blue rows and blue columns. What is the highest possible score for Anna?

  3. Nick’s Mathematical Puzzles ☆☆☆

    Two players play the following game with a fair coin: Player 1 chooses and announces a triplet of results that might result from three successive tosses of the coin — HHH, HHT, THT, etc. Player 2 then chooses a different triplet. The players toss a coin until one of the player’s triplets appears. The triplets may appear in any three consecutive tosses and the winner is the player whose triplet appears first.
    1. What is the optimal strategy for each player? With best play, who is most likely to win?
    2. Suppose the triplets were chosen in secret? What then would be the optimal strategy?
    3. What would be the optimal strategy against a randomly selected triplet?

  4. MIT

    Alice and Bob play the following game. They begin with a sequence \((a_1,\dotsc,a_{2n})\) of positive integers. The players alternate turns, with Alice moving first. When it is someone’s turn to move, that person can remove either the first or last remaining term of the sequence. A player’s score at the end of the game is the sum of the numbers they removed. Show that Alice has a strategy that guarantees a score at least as large as Bob’s.

  5. Putnam 2002 B2

    Consider a polyhedron with at least five faces such that exactly three edges emerge from each of its vertices. Two players play the following game: Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who first succeeds in signing three faces that share a common vertex. Show that the player who signs first will always win by playing as well as possible.

  6. Putnam 2020 B2

    Let \(k\) and \(n\) be integers with \(1 \leq k \lt n.\) Alice and Bob play a game with \(k\) pegs in a line of \(n\) holes. At the beginning of the game, the pegs occupy the \(k\) leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice playing first. The game ends when the pegs are in the \(k\) rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of \(n\) and \(k\) does Alice have a winning strategy?

  7. 1990 Leningrad Mathematics Olympiad

    Anna and Boris play a game starting with the number 1234. Anna goes first, and turns alternate thereafter. In each turn, the player subtracts from the number one of its non-zero digits. A player wins if the number is reduced to 0. Who has a winning strategy, Anna or Boris?

  8. Putnam 2013 B6

    Let \(n \gt 1\) be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of \(n\) spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either

    • places a stone in an empty space, or
    • removes a stone from a nonempty space \(s,\) places a stone in the nearest empty space to the left of \(s\) (if such a space exists), and places a stone in the nearest empty space to the right of \(s\) (if such a space exists).

    Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn?

  9. Putnam 2006 A2

    Alice and Bob play a game in which they take turns removing stones from a heap that initially has \(n\) stones. The number of stones removed at each turn must be one less than a prime number. The winner is the player who takes the last stone. Alice plays first. Prove that there are infinitely many \(n\) such that Bob has a winning strategy. (For example, if \(n=17\), then Alice might take 6 leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win.)

  10. Putnam 2008 A2

    Alan and Barbara play a game in which they take turns filling entries of an initially empty \(2008 \times 2008\) array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

  11. Putnam 1995 B5

    A game starts with four heaps of beans, containing 3,4,5 and 6 beans. The two players move alternately. A move consists of taking either one bean from a heap, provided at least two beans are left behind in that heap, or a complete heap of two or three beans. The player who takes the last heap wins. To win the game, do you want to move first or second? Give a winning strategy.