Transversal achievement game on a square grid

Importance: Medium ✭✭
Author(s): Erickson, Martin
Subject: Combinatorics
Keywords: game
Recomm. for undergrads: yes
Posted by: Martin Erickson
on: June 29th, 2010

\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}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.

Are there a simple solution?

I suspect, there are no simple answer and it can be solved only by heavy calculations, that is essentally there is no solution to this problem.

history and application

i'm not sure but i think to solve this problem, i was wondering if any body gives me some information about the history and application of this problem

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.