Erickson, Martin


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

Exact colorings of graphs ★★

Author(s): Erickson

\begin{conjecture} For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph (that is, a coloring with $c$ colors all of which must be used at least once), there exists an exactly $m$-colored countably infinite complete subgraph. Then $P(c,m)$ is true if and only if $m=1$, $m=2$, or $c=m$. \end{conjecture}

Keywords: graph coloring; ramsey theory

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

Sequence defined on multisets ★★

Author(s): Erickson

\begin{conjecture} Define a $2 \times n$ array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array $[1; 1]$, the sequence is: $[1; 1]$ -> $[1; 2]$ -> $[1, 2; 1, 1]$ -> $[1, 2; 3, 1]$ -> $[1, 2, 3; 2, 1, 1]$ -> $[1, 2, 3; 3, 2, 1]$ -> $[1, 2, 3; 2, 2, 2]$ -> $[1, 2, 3; 1, 4, 1]$ -> $[1, 2, 3, 4; 3, 1, 1, 1]$ -> $[1, 2, 3, 4; 4, 1, 2, 1]$ -> $[1, 2, 3, 4; 3, 2, 1, 2]$ -> $[1, 2, 3, 4; 2, 3, 2, 1]$, and we now have a fixed point (loop of one array).

The process always results in a loop of 1, 2, or 3 arrays. \end{conjecture}

Keywords: multiset; sequence

Syndicate content