You find a drawing of an interrupted game of tic-tac-toe (noughts and crosses).
You know that each player was an expert, which means that none of them ever puts herself into a potentially losing position and that each always wins if her opponent gives her the opportunity.
There are two Xs and two Os in the diagram, and it is impossible to tell
whose move it is.
Ignoring symmetry, what is the position?
Source: David L. Silverman:
Solution (ending revised)
Note: in the stuff below, x and o are everywhere at once interchangeable.
We use the constraint on possible patterns that neither player may make a winning fifth move of the game, nor even secure a win on the fifth move of the game. (More on this at the end.)
There are only eight patterns the two x's can make (considering symmetry)
1. 2. 3. 4. 5. 6. 7. 8.
___ x__ x_x x__ xx_ _x_ x__ _x_
x_x ___ ___ _x_ ___ _x_ ___ x__
___ __x ___ ___ ___ ___ _x_ ___
Now we put o's where they must appear, or else
on the fifth move x will win.
1. 2. 3. 4. 5. 6. 7. 8.
___ x__ xox x__ xxo _x_ x__ _x_
xox _o_ ___ _x_ ___ _x_ ___ x__
___ __x ___ __o ___ _o_ _x_ ___
We can immediately throw out cases 1 and 2, since wherever the other o is placed, o will then win if o then makes the fifth move.
Now we put placeholders (a and b) in cases 3, 4, 5, and 6, where the second o may be placed without making the next move a winning move for o. (We don't list the symmetric placements.) These are the only candidate patterns we need to consider.
3. 4. 5. 6.
xox xa_ xxo ax_
a__ _x_ a__ bx_
b__ __o _b_ _o_
We number the grid:
and we check the cases again by, say, in case 3, putting an o in position 3a or 3b. Then we state what can happen in the fifth move.
3a. x to 9 secures win.
3b. x to 9 secures win.
4a. x to 7 secures win.
5a. x to 5 secures win.
5b. o to 7 secures win.
6a. o to 7 secures win.
6b. x to 3 secures win.
Cases 7 and 8 remain. Case 7 breaks into 7 distinct cases:
7.I 7.II 7.III 7.IV 7.V 7.VI 7.VII
xo_ x_o x__ x__ x__ x__ x__
___ ___ ___ o__ _o_ __o ___
_x_ _x_ ox_ _x_ _x_ _x_ _xo
We add potential last o's again:
7.I 7.II 7.III 7.IV 7.V 7.VI 7.VII
xoa xao xa_ xab xa_ xa_ xa_
bcd b__ b_c o__ _o_ __o bc_
exf _x_ oxd cxd _xb bx_ dxo
7.Ia: x to 7 secures win.
7.Ib: x to 7 secures win.
7.Ic: x to 7 secures win.
7.Id: x to 7 secures win.
7.Ie: tie?
7.If: tie?
7.IIa: x to 7 secures win.
7.IIb: x to 5 secures win.
7.IIIa: tie?.
7.IIIb: x to 2 secures win.
7.IIIc: x to 2 secures win
7.IIId: x to 2 secures win.
7.IVa: x to 7 secures win.
7.IVb: x to 7 secures win.
7.IVc: x to 5 secures win.
7.IVd: x to 2 secures win.
7.Va: x to 7 secures win.
7.Vb: o to 6 secures win.
7.VIa: x to 7 secures win.
7.VIb: x to 2 secures win.
7.VIIa: tie?
7.VIIb: x to 2 secures win.
7.VIIc: o to 3 secures win.
7.VIId: o to 3 secures win.
Case 8 breaks in 5 distinct cases.
8.I 8.II 8.III 8.IV 8.V
ox_ _xo _x_ _x_ _x_
x__ x__ xo_ x_o x__
___ ___ ___ ___ __o
They have spots for the remaining o that are not secure wins if o
has the fifth move:
8.I 8.II 8.III 8.IV 8.V
oxa axo _x_ ax_ _x_
x_b x__ xoa xbo x__
___ _b_ ___ cd_ __o
8.Ia: x to 5 secures win.
8.Ib: o to 9 secures win.
8.IIa: x to 5 secures win.
8.IIb: o to 7 secures win.
8.IIIa: x to 1 secures win.
8.IVa: o to 9 secures win.
8.IVb: o to 9 secures win.
8.IVc: o to 9 secures win.
8.IVd: o to 9 secures win.
8.V: Wherever the remaining o is placed, o will win on the fifth move.
Now we look back and see that 7.Ie is the same as 7.IIa and 7.If is the same as 7.VIIa. So there are only two qualifying patterns.
It is worth recapping the two different ways we have thrown out all the other patterns:
If both of the players can win or secure a win on the fifth move (if they are the one going next) then they have not been playing like pros by allowing this to happen. If only one can secure a win on the next move, either the other has not been playing like a pro or else we know who will actually go next (the other player). Either way, such a game fails meet the constraints.
We have also assumed that if a win is not secured by the fifth move, the game will draw - this is true for even poor players and never even comes up for pros.
So, we are left with only two rather dubious four move patterns possible (while remembering that x and o may be reversed):
*********************
*
Soln. 1. Soln. 2. *
*
xo_ xo_ *
___ and ___ *
_xo ox_ *
*
*********************
Played professionally, there will be no winner in these no matter whose turn it is. But how did these boards get to these states?
Remembering symmetries, and that either player could go first in these, there are only four possible ways to get to each board: First player starts with the top left move (or top right) and the second player replies on top (or on bottom), and so, after that, the last two moves, #3 and #4, are predetermined. We will call these four games LT, RT, LB, RB.
The LT and LB games are senseless and can be ignored considering the possible history of the games, since the winning third move was not played (see below). The RT and RB games however are no better than any other games that end in draws, since for pros, they are not winnable. Neither of these two (rather lame) games above is thus better than the other, and both must be considered as answers to the puzzle. (Unless I missed something...)
Here are all the games and the missed winning tactics:
Solution 1.
LT-tie
x xo xo_ xo_
___ ___ ___ ___
___ ___ _x_ _xo
LT-win
x__ xo_ xo_ xo_ xo_
___ ___ ___ o__ o__
___ ___ x__ x__ x_x
LB-tie
x__ x__ x__ xo_
___ ___ ___ ___
___ o__ ox_ ox_
LB-win
x__ x__ x_x xox xox
___ ___ ___ ___ ___
___ o__ o__ o__ o_x
RT-Tie
_x_ ox_ ox_ ox_
___ ___ ___ ___
___ ___ x__ xo_
RB-Tie
_x_ _x_ _x_ _xo
___ ___ ___ ___
___ _o_ _ox _ox
Solution 2.
LT-Tie
x__ xo_ xo_ xo_
___ ___ ___ ___
___ ___ _x_ _xo
LT-Win
x__ xo_ xo_ xo_ xo_
___ ___ _x_ _x_ _x_
___ ___ ___ __o x_o
LB-Tie
x__ x__ x__ xo_
___ ___ ___ ___
___ __o _xo _xo
LB-Win
x__ x__ x__ x__ x_x
___ ___ ___ o__ o__
___ __o x_o x_o x_o
RT-Tie
_x_ ox_ ox_ ox_
___ ___ ___ ___
___ ___ __x _ox
RT-Tie
_x_ _x_ _x_ ox_
___ ___ ___ ___
___ _o_ _ox _ox
-fin-
Edited on November 9, 2018, 2:35 pm
soln?
