All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Reverse reasoning (Posted on 2018-11-01)
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:

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 soln? | Comment 1 of 3
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:

1 2 3
4 5 6
7 8 9

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
 Posted by Steven Lord on 2018-11-05 10:40:15

 Search: Search body:
Forums (0)