NSA's 2018 Puzzle Periodical
Try your hand at this month's problem written by a member of our expert workforce.
Creator Challenge Difficulty Rating: Hard
Puzzle created by Stefan T., NSA Research Mathematician
This month's NSA Puzzle Periodical pays tribute to the 1983 motion picture "WarGames." In the movie, a supercomputer is programmed to play Tic-Tac-Toe.
The computer plays itself, with each X and O placed uniformly at random into any square (this means the computer plays without regard to strategy). What is the probability a game will end in a draw?
Assume perfect random number generation. The first X will be placed in any square with probability 1/9. The first O will go into any of the remaining squares with probability 1/8, and so on.
Answer: The probability of a draw is 8/63.
If we number the squares of the board 1 to 9,
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
then every permutation of 1 through 9 defines a game. For instance, the permutation 178294635 would be the game where X plays in square 1, then O plays in square 7, then X in square 8, and so forth. This would result in
X | O | O |
O | X | X |
O | X | X |
which is a win for X. It follows that there are 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 possible games. (Note, the order is important in determining the winner. If the final layout were
X | X | X |
O | O | O |
X | O | X |
then the winner would be the one who completed its row first.)
However, we're interested in ties, so we just need to count how many of these games result in no winner. All we need to do is consider the possible locations of the "O"s in a tie. There must be at least one O (but fewer than three!) in every row, column, and diagonal. Up to symmetry, there are 3 distinct placements of the "O"s that will achieve this: (Here, two positions of the board are considered related by symmetry if one can be obtained from the other by a combination of rotations by 90 degrees of the entire board and flipping the entire board around the vertical axis containing positions 2, 5, and 8.)
O | X | X |
X | O | O |
X | O | X |
O | X | O |
X | X | O |
X | O | X |
O | X | O |
X | O | X |
X | O | X |
For instance, position 1 means O goes in squares 1,5,6,8, while X goes in squares 2,3,4,7,9. Because the order the "X"s and "O"s are placed doesn't matter, there are 4! × 5! ways to arrive at this position. Then, notice that position 1 has a 4-fold rotational symmetry:
O | X | X |
X | O | O |
X | O | X |
X | X | O |
O | O | X |
X | O | X |
X | O | X |
O | O | X |
X | X | O |
X | O | X |
X | O | O |
O | X | X |
so that there are actually 4 × 4! × 5! draws resulting in position 1. Position 2 has an 8-fold rotational/reflective symmetry so there are 8 × 4! × 5! ties resulting in position 2.
Finally, position 3 has a 4-fold symmetry so there are 4 × 4! × 5! games that will end in a tie in position 3. All told, there are 16 × 4! × 5! games that will end in a draw. Thus, the probability of a draw is (16 × 4! × 5!)/9! = 8/63.
Did you enjoy this NSA Puzzle Periodical?
If your friends and family would also like to try this math and logic challenge, look for NSA's Puzzle Periodical on the third Tuesday of every month on www.nsa.gov.
NSA's Puzzle Periodical is also Tweeted to more than 400,000 + followers.
NSA Resources