Checkers on a Chessboard Given 2k pieces on a k by k chessboard, prove that there is always a sequence of pieces $K_1, K_2 \ldots K_{2n}$ such that $K_1$ and $K_2$ are in the same row, $K_2$ and $K_3$ are in the same column, $K_3$ and $K_4$ are in the same row ... $K_{2n-1}$ and $K_{2n}$ are in the same row, and $K_{2n}$ and $K_1$ are in the same column. This sequence does not necessarily contain all the pieces on the board.
 A: Another way to do this is motivated by graph theory.
Let $R=\{r_1,r_2,\dots, r_k\}$ and $C=\{c_1,c_2,\dots,c_k\}$, and consider $R\cup C$ as a set of vertices. For each position $(i,j)$ on the chessboard with a checker, draw an edge between the vertices $r_i$ and $c_j$. This will create a graph with $2k$ vertices and $2k$ edges. A graph with at least as many edges as vertices must contain a cycle. Follow the cycle (which must alternate between vertices in $R$ and vertices in $C$ by construction, so must have even length) to get your sequence. 
A: Note that the length of the sequence is unimportant. What matters is that we can always continue the sequence in a nontrivial way. Any such sequence can be continued forever giving a "circuit" on the chessboard.
We will prove this by induction. Our base case is the $2\times 2$ chess board, where the solution is obvious because every square has a piece on it. Now we consider an $n\times n$ chess board.
Case 1: Every row and column has exactly 2 pieces in it. We can start anywhere on the board, and we're guaranteed to be able to find our sequence.
Case 2: There exists a row (or column) with fewer than 2 pieces. We'll assume without loss of generality that there is a row, $r$, with fewer than 2 pieces. Subcase i: (There are no pieces in row $r$) The average number of pieces is a column is 2 because there are $2n$ pieces and $n$ columns. Find a column with 2 pieces. Delete row $r$ and the column with 2 pieces, obtaining an $(n-1)\times(n-1)$ checkerboard with $2(n-1)$ pieces. Subcase ii: (There is one piece in row $r$) If the column containing the piece in row $r$ has only 2 pieces, then row $r$ and column containing the piece in row $r$. Otherwise that column has $3$ pieces, so there is a column with only one piece. Delete row $r$ and the column with one piece. We then obtain an $(n-1)\times (n-1)$ checkerboard with $2(n-1)$ pieces. By induction, the proof is complete.
Edited to note that when I say "delete a row and column", I mean ignore them and find a sequence on the resulting $(n-1)\times (n-1)$ chessboard.
