1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Double Tic-Tac-Toe Strategy

  1. Feb 15, 2012 #1
    1. The problem statement, all variables and given/known data
    Consider the game of `double move tic-tac-toe' played by the usual rules of tic-
    tac-toe, except that each player makes two marks in succession before relinquishing
    his turn to the other player (you may know tic-tac-toe by the name `noughts and
    crosses'). Prove that there exists a strategy by which the first player always wins.

    2. Relevant equations
    None that I can think of.

    3. The attempt at a solution
    I have no clue how to prove this. The obvious strategy is that player one places an X at one of the corners of the board and then one in the center. Player two can't block all the winning strategies with their two moves.

    The question is, how do I show this in "math speak"?

    Thanks! Sorry for all the posting lately, I'm just terrible at Discrete Math.
  2. jcsd
  3. Feb 15, 2012 #2
    After the first turn the board looks like

    |X| | |
    | |X| |
    | | | |

    Where do player 2 need to place O's for you not to be able to win in your turn? Can this be done with just 2 O's? If you can find three disjoint sets of spots that must each be blocked, then you are finished.

    In other words, can you partition the last 7 empty spaces into 3 disjoint subsets such that if any of the 3 disjoint subsets are left untouched by player 2, then you can win in your turn?
  4. Feb 15, 2012 #3


    User Avatar
    Science Advisor

    obviously, player 2 cannot win in 1 move (he only can place two marks).

    since player 2 cannot win on their first move, their best strategy is to prevent player 1 from winning on player 1's second move.

    player 2 must place a mark at (3,3), or else player 1 will on the next move, and then win.

    there are 4 possible ways player 1 might place two marks and win on their next move, given that (3,3) is taken: complete the center row, complete the center column, or complete the left column, or the top row. player 2 must block all 4 of these possibilities with a single move.

    show that player 2 can at most only block 2 of these.

    a slightly more challenging question is: suppose player 1 allows player 2 to make his first move for him (still using X's for player 1, and O's for player 2. player 2 does NOT get to place 4 O's). does player 1 still always have a winning strategy?
  5. Feb 16, 2012 #4
    |x| | |
    | | | |
    | | |x|

    In this case player two can never win because you have three rows to win, right?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook