13
$\begingroup$

Here's a problem I assigned to my graph theory class. The only caveat is that I insisted that their solutions be entirely graph theoretic. Have fun with it.

Prove that a game of Tic-Tac-Toe played on the torus can never end in a draw.

The idea is to simulate the game (toroidal Tic-Tac-Toe) as a $2$-edge-coloring game on a certain bipartite graph. A win here would be tantamount to saturating a single (specific type of) vertex with edges all of one color.

This has nothing whatsoever to do with stategy or perfect play. The standard rules of Tic-Tac-Toe apply (horizontal, vertical, and diagonal wins), except that on the torus there are four additional diagonal wins.

As an example, if one coordiantes the squares of the Tic-Tac-Toe board as $(i,j)$ with $1\le i,j\le 3$, then the set $\{(1,2),(2,3),(3,1)\}$ constitutes a diagonal win on the torus. (Note that we are assuming that the Tic-Tac-Toe board covers the entirety of the torus.)

Remember that we're requesting that the proof be purely graph-theoretic, despite that it would be far easier to just list all possible endgames and note that there are no draws occurring. (PS: I have a solution to this problem.)

$\endgroup$
9
  • 1
    $\begingroup$ What does it mean for the proof to be graph theoretic? Is it ok to prove that no five-position configuration is winless, but only if the proof does not consider each position independently? $\endgroup$
    – Steve Kass
    Nov 22 '13 at 6:13
  • $\begingroup$ Very nice problem. I think I have a solution too. It still has a certain amount of case analysis, but the main graph-theoretic tool is (rot13) Enzfrl'f gurberz: n avar-pyvdhr pbagnvaf n erq gevnatyr be n oyhr sbhe-pyvdhr. Is that how yours goes also? $\endgroup$ Nov 22 '13 at 7:31
  • $\begingroup$ @Steve, I edited the problem with a bit of a starting context, as I felt that "graph theoretic proof" might be too opaque and in need of some clarification. $\endgroup$
    – Doc
    Nov 22 '13 at 15:10
  • $\begingroup$ @Nate, interesting! If I interpret you correctly, I'm not sure how you would define adjacency so that what your approach would work. (PS: Was not familiar with rot13, and at first thought you were speaking Clingon :-) ) $\endgroup$
    – Doc
    Nov 22 '13 at 15:11
  • $\begingroup$ Ok, so I guess my proof is different from yours! If I get a chance in the next few days, I'll try to write it up nearly and post it. $\endgroup$ Nov 22 '13 at 15:45
5
$\begingroup$

Let us re-interpret the tic-tac-toe game in terms of edge coloring for two associated graphs.

Note that there are $12$ total ways to win on the torus. There are $3$ horizontal lines and $3$ vertical lines. Analogously, there are $3$ diagonal lines and $3$ anti-diagonal lines. Each horizontal/vertical line pair uniquely determines a cell through their intersection. Conversely each cell belongs to precisely one such pair. The same holds for the diagonal/anti-diagonal pairs.

Let there be $6$ vertices on our first graph, one for each vertical/horizontal line. Join each vertical vertex to each horizontal vertex. The result is the complete bipartite graph $K_{3,3}$ where each edge corresponds to a cell on the playing grid. Construct the second graph through the same procedure for diagonal/anti-diagonal lines.

Now the game can be interpreted as $2$-coloring the edges of the graphs (where each move colors an edge on both graphs). Winning the game corresponds to saturating a vertex on one of the two graphs with edges of the same color. The key is now to note the following two facts:

  1. If there exists a perfect matching with edges of the same color on one graph, then this necessarily implies the existence of a vertex saturated with the same color on the other graph.

  2. If every vertex of $K_{3,3}$ is adjacent to edges of both color then there necessarily exists a perfect matching with edges of the same color.

It's not very difficult to prove the above two facts and I will not do so here (although the proof I have still requires a bit of case-checking, if anyone has an elegant proof of the two facts above, please share it with me). The overall interpretation here is that the game on the torus brings in a duality between vertical/horizontal wins and diagonal/anti-diagonal wins. Not winning one way forces a win the other way.

$\endgroup$
3
  • $\begingroup$ I like what you've done here. Let me add something to your proof. One of the players has five moves, so let's consider that player's five edges in one $K_{3,3}$. Case one: These edges make a spanning tree. As you pointed out, we need to avoid a vertex saturated of either color, hence the tree is a path on 6 vertices, and we have the desired matching. Case two: The five edges do not make a spanning tree. As $K_{3,3}$ is bipartite, this leaves only one possibility: They induce a $C_4 + K_2$. Again we have our matching. (Btw, my proof was quite different from yours.) Nice job. $\endgroup$
    – Doc
    Nov 22 '13 at 22:43
  • $\begingroup$ @Doc Ah that's a nice way to finish off. What I had in mind was to remove the edges of one color. The remaining graph has vertices of degree at most $2$ and so is a union of paths and cycles. It's rather easy to check at this point that the only case where we don't have a perfect matching is when the remainder is $P_3 + P_3$ whereupon we can find a matching with the edges we've removed. By the way, if you could post your proof as well, I'd like to see how you solved the problem. $\endgroup$
    – EuYu
    Nov 22 '13 at 22:52
  • $\begingroup$ I just posted it. I hope none of my students is looking :-) $\endgroup$
    – Doc
    Nov 23 '13 at 3:29
4
$\begingroup$

I'm not too certain what constitutes purely graph theoretic. Here is a proof that doesn't use cases.

We will show that given 5 points, there must be 3 that form a line.

Order the points $p_i$ (in whatever order you wish). Consider the pair wise difference of points $p_i - p_ j$ for $i> j$, Taken modulo 3. There are 5 points hence 10 pairs, but only 9 possibilities for their difference, thus 2 pairs of differences must be the same.

If the 2 pairs share a common point, it must be the middle point which is common, hence we get 3 points on a line and we are done.

If the 2 pairs do not share a common point, we have a parallelogram. By applying a change of basis and translation, we may assume WLOG that the points are the (1,1) (1,2) (2,1) (2,2). It is now clear that no matter where the fifth point is, we will always have a line. Hence done.

$\endgroup$
1
  • $\begingroup$ I like your proof. It doesn't use any graph theory though. Nonetheless, +1. $\endgroup$
    – Doc
    Nov 22 '13 at 21:24
2
$\begingroup$

Well, I'll post this solution anyway, although it's not as good. You might find it helpful to have some colored pens handy as you read it.

Consider the nine squares of the tic-tac-toe torus as the vertices of a graph $G$. Every square is adjacent to every other square, either horizontally, vertically, or diagonally, so if we draw an edge between all vertices corresponding to adjacent edges, we have the complete graph $K_9$. We will use C to denote an edge that is either horizontal or vertical, and D for a diagonal edge. (C might stand for Cartesian; I couldn't think of better words.) Suppose the game has finished, so every vertex is marked with either an X or an O. We will call an edge friendly if it joins two X or two O vertices, and otherwise we call it hostile.

Color the edges of our $K_9$ as follows: all friendly C and hostile D edges are colored red, and all remaining edges (hostile C and friendly D) are colored blue. Now it is known that the Ramsey number $K(3,3)$ is $6 \le 9$ and therefore our $K_9$ must contain either a red triangle or a blue triangle.

Suppose it contains a blue triangle. The red triangle case is isomorphic, since here is an isomorphism that interchanges C and D type wins:

123    195
456 -> 843
789    627

Consider the blue triangle. By parity, it must be that an odd number of these 3 edges are friendly (hence type D). If all edges are friendly D, we have three X's or three O's in the same diagonal, and we are done. Otherwise, it contains two hostile C edges and one friendly D. This must correspond to a configuration like:

...
X..
OX.

up to isomorphism. But any board containing this configuration must have a winning position. For if we try to fill in the remaining squares to avoid either player winning, we are forced to do

...    ..O    ..O    .OO
X.. -> X.. -> XX. -> XXO
OX.    OX.    OX.    OO.

and we see that after all we cannot avoid a winning position.

In fact we can say more: $K(3,4) = 9$ so the board must contain a red triangle or a blue $K_4$. But assuming a monochromatic $K_4$ doesn't seem to make things any easier than a triangle.

$\endgroup$
1
  • $\begingroup$ Very clever. I only wish that the last portion of the proof didn't deviate from the very nice graph theoretic flavor that led you to that point. +1 $\endgroup$
    – Doc
    Nov 22 '13 at 23:11
1
$\begingroup$

Consider the bipartite graph $G$ with bipartition $V(G)=\mathcal S\cup\mathcal W$, where $\mathcal S$ consists of the $9$ squares $s_i$ ($1\le i\le 9$) of the Tic-Tac-Toe board, and $\mathcal W$ consists of the $12$ triples $\{s_i,s_j,s_k\}$ that represent winning positions. Note that each square has degree $4$, while each winning triple has degree $3$.

Assume we are given a $2$-edge coloring that corresponds to a game-ending draw. Assume Player B (the second player to go) has colored his edges blue, and consider the "blue" graph, denoted $\mathcal B$. For convenience, rename the squares in graph $\mathcal B$ as $b_1,b_2,b_3,b_4$. Clearly $\mathcal B$ has 16 edges since $deg_{\mathcal B}(b_i)=4$ for $1\le i\le 4$.

Observe that $1\le deg_{\mathcal B}(T)\le 2$ for all $T\in \mathcal W$, since $deg_{\mathcal B}(T)=0$ indicates a win for Player A, and $deg_{\mathcal B}(T)=3$ indicates a win for Player B. But this implies that there exists $T^*\in\mathcal W$ with $deg_{\mathcal B}(T^*)=2$. Indeed, otherwise graph $\mathcal B$ would have only $12$ edges, a contradiction. Without loss of generality, write $T^*=\{b_1,b_2,a\}$ where $a$ is a square played by Player A. Let $T_1,T_2,T_3\in \mathcal W$ be the other three triples that contain $a$.

Now consider the subgraph of $\mathcal B$ induced on the set $\{b_1,b_2,b_3,b_4,T^*,T_1,T_2,T_3\}$. This graph must have at least $5$ edges, since $deg_{\mathcal B}(T^*)=2$ and $deg_{\mathcal B}(T_i)\ge 1$ for $1\le i\le 3$. Thus there exists $b_j$ with $deg_{\mathcal B}(b_j)\ge 2$.

But now, returning to graph $G$, this creates a $4$-cycle with $b_j$ and $a$ as antipodal vertices. (Recall that $a$ is adjacent to all of $T^*,T_1,T_2,T_3$.) This is our final contradiction, since any two squares of the Tic-Tac-Toe board determine a unique winning triple.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.