# game

## Transversal achievement game on a square grid ★★

Author(s): Erickson

\begin{problem} Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $n \times n$ grid. The first player (if any) to occupy a set of $n$ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play? \end{problem}

Keywords: game

## Square achievement game on an n x n grid ★★

Author(s): Erickson

\begin{problem} Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $n \times n$ grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play?

Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15. \end{problem}

Keywords: game

## A gold-grabbing game ★★

Author(s): Rosenfeld

\textbf{ Setup} Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of \emph{gold} at $v$.

\textbf{2-Player game} Players alternate turns. On each turn, a player chooses a leaf vertex $v$ of the tree, takes the gold at this vertex, and then deletes $v$. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

\begin{problem} Find optimal strategies for the players. \end{problem}

Keywords: game; tree