Noughts and Crosses

Firstly, the results for the Balkan Mathematical Olympiad have been published. Consequently, the preliminary UK IMO squad is now larger than ever before, comprising ten people (six team members and four reserves, in some indeterminate order).

You are probably aware of the game of Noughts and Crosses (alternatively referred to as tic-tac-toe), in which one attempts to seize three collinear squares whilst attempting to prevent one’s opponent from doing likewise. What is less well-known, albeit mentioned in the Royal Institution Christmas Lectures several years ago, is that it’s entirely equivalent to the following problem:

We begin with the numbers {1, 2, 3, … 9}. Players alternate turns, taking an available (unclaimed) number. The first player to obtain three numbers which sum to 15 is declared the winner.

To demonstrate their equivalence, it suffices to show that we can label the squares from 1 to 9, inclusive, such that every sum to 15 corresponds to a unique line, and vice-versa. This is accomplished by the following magic square:

noughts

It is immediate from the definition of the magic square that all lines (sets of three collinear squares) consist of three distinct numbers in the range {1, 2, …, 9} summing to 15. What is less obvious is the converse, that every such set is represented by a line. I only just realised the real reason behind this, which hitherto seemed to be a mere coincidence. Firstly, we decrement each of the numbers by 5, so that all line sums are zero.

noughts2

Now, think of these as points rather than squares. For convenience, we shall allow 0 to be the origin. On the diagram below are the curves x(x − 1)(x + 1) = 0, y(y − 1)(y + 1) = 0, and the linear combination x(x − 1)(x + 1) = 2y(y − 1)(y + 1). The latter must also pass through all nine grid points, being a combination of the other two.

noughts4

This is an elliptic curve, so it admits a well-known Abelian group structure. We chose the coefficient 2 in the equation for the curve specifically so that the tangent at -1 intersects the elliptic curve again at 2; similarly, the tangent at -2 intersects the curve again at 4. From this and the remaining lines, it is easy to see that the elliptic curve group operation corresponds to ordinary integer addition. And we know that three points on an elliptic curve sum to zero if and only if they are collinear (c.f. my elliptic curve calculator, which was recently made into a video by James Grime of DAMTP):

Anyway, generalising this idea, we can show that the following two games are equivalent:

  • Generalised Noughts and Crosses, where the squares are positioned at non-torsion points on an elliptic curve and you win with three collinear copies of your symbol;
  • A game in which you and your opponent alternate taking numbers from a predetermined set, and attempt to obtain three numbers summing to a predetermined total.

By looking through the Elliptic Curves on a Small Lattice, I found a game of Generalised Noughts and Crosses on a reasonably small grid corresponding to the game where you attempt to form a total of 27 from three numbers in the range {1, 2, 3, …, 17}:

17-points

You can verify for yourself that sets of three collinear squares are in bijective correspondence with sets of three numbers in the range {1, 2, …, 17} summing to 27.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s