Tic Tac Toe

Computer Science Level pending

Jack and Jill are playing a game of Tic-Tac-Toe, where both are trying to win and can only make legal moves. Jacob came along, and saw that their board was in the above situation. Which player will win the game?

You do not know which player started first.

X Cannot be determined until the next turn's player is not known O None of the above

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Discussions for this problem are now closed

Pankaj Joshi
Mar 15, 2014

I suggest everyone to draw the question figure before reading the solution and mark the places from left to right as:

           1 2 3

           4 5 6

           7 8 9.

At 1 , 4 and 9 there is O and at 2, 7, and 8 there is X.

Alright , we do this question by finding out which person shall get the next chance by ruling out wrong possibilities.

Let us assume for once that X got the 6th chance . Let the X at 2 was his last chance. But we know he wants to win so instead of putting an X at 2 , he could have stopped O from completing the diagonal by putting a X at 5. So this possibility is ruled out.

Now let us assume that X put his last chance at 7. This might seem a legit move for stopping O to complete the left vertical. But instead of stopping O, he could have himself won by putting a X at 5 and completing the mid vertical , hence winning. So, this possibility is also ruled out.

The last possibility (putting an X at 8 ) is similar to our first assumption , he could have put a X at 5 and stopped O from completing the diagonal.

Thus ruling out all the possibilities of X getting the 6th chance , we conclude that only O could have got the 6th chance.Hence next turn is X's. He wins by putting a X at 5...

So much of typing!!! Tiring Solution :( !

By symmetry of the situation I could say that it is indeterminate

Arnab Acharya - 7 years, 2 months ago

What if O got the 6th chance?? Then why O didn't put at 5??

Doo Young Kim - 7 years, 2 months ago

Probably because the 6th move was to block X by placing an O in position 9.

It wouldn't make sense for the O at position 4 to be the 6th move because that would have meant the O missed a very easy way to win. And the O in position 1 wouldn't have been the 6th move because it would have been clearly better to place the O at 5 instead of 1. Therefore, the 6th move was probably placing an O on 9.

Ben Wilson - 7 years, 2 months ago

This problem doesn't say players don't lack sense. So we could say it is indeterminate.

Micah Wood - 7 years, 2 months ago

@Micah Wood Haha nice one :)

Paul Paul - 6 years, 10 months ago

This solution seems slightly incomplete to me: You showed that "O went first" isn't compatible with the assumptions; but you should go on to show that "X went first" is compatible with the assumptions. (If it isn't, we must conclude "None of the above.")

Peter Byers - 7 years, 2 months ago

I believe it's "Cannot be determined until the next turn's player is known." Because one of them should be winner. But I think both your and my answer could be correct.

Micah Wood - 7 years, 2 months ago

It is human psychology, the 1st one always moves with X.

Ali Zia - 7 years, 2 months ago

I just played the game one time starting from O and it won lol

siddharth shah - 7 years, 2 months ago

Very good solution. I thought that we couldn't tell, but when I reread the problem I saw that each player is trying to win and, therefore, we can eliminate which options could not have been made last. By extending your argument, it can be shown that the only reasonable solution for the 6th move would have to be the O at position 9.

Ben Wilson - 7 years, 2 months ago

this problem just like betting problem because there's no any official rule which is going to be the first, X or O..

Krisna Attayendra - 7 years, 2 months ago

nice, tricky problem.

Hữu Nguyễn - 7 years, 2 months ago

Well it took me 10 seconds to chose my answer. Its always X to take the first turn and since theres 3 X and 3 O XOXOXO...X!

its sometimes called XOX game not OXO.

Its a game where deciding who take the first turn is not X or O, its who will be X and who will be O. If you are X, theres a clear high 98% chance you will be first. IDK its in our mind.

Roi Vinson Abrazaldo - 7 years, 2 months ago

I think the first player to occupy the center would win. That would place both the players at equal odds and the only deciding factor would be who would play first. Is my argument rational? Please advise.

Sanjay kamath - 7 years, 1 month ago

Well, if the second one puts it on an edge then the first one would place it on a corner not neighbouring the edge (and through a "chain", having the attention too, the first one will certainly win). I don't know how to win if the 2nd places his move on a corner... (I still get ties)

Paul Paul - 6 years, 10 months ago

The game situation looks like

1   2   3 
4   5   6  
7   8   9

it seems like first O put on 1, then X put on 2. When on third chance O put on 4, to stop its winning X put on 7. Then O put on 9, to make a possibility of X's triplet he placed on 8 to make triplet of 2,5,8 . Considering 6th chance is of O he will definitely place on 5 to stop X's winning triplet. Then to stop O's winning triplet i.e 4,5,6, X will place on 6. O will end on placing at 3. This will end the game at draw stage. So, I think none of them would win.

Nimisha Soni - 7 years ago

Well, the 6th move has already been done and it wasn't on 5 :)

Paul Paul - 6 years, 10 months ago
Ivan Koswara
Mar 24, 2014

This should be the intended solution:

Observe that both players can win by playing in the center position, and clearly since the players are playing for win, they won't leave such open line. The only possibility is that a person created two threats at once and his opponent blocks one threat, leaving the other, the one involving the center, open.

Suppose O created the double threat. Then he must have played on top-left, replied by X playing on bottom-left. But then in the position before that, X would have a threat on its own (vertical middle) which is not blocked by O, contradiction. Thus X created the double threat by playing on bottom-middle, and O blocked one line on bottom-right. Thus X will win by playing on the central square.

However , it has been proven that tic-tac-toe is a draw, so some player must have made a mistake. Indeed, whatever second move O played have let X to win by playing at bottom-middle, so O's second move (or perhaps first move) gave X the win, and thus this position shouldn't have occurred.

Here's the full analysis. Denote the spots with numbers, like in Pankaj's solution:

1 2 3
4 5 6
7 8 9

We also know X played 8 on his third move and O replied with 9.

If X played on 7, then whatever O's move was a mistake:

  • 7 4? 5! 3 8 (double threat 2/9)
  • 7 1? 9! 8 3 (double threat 5/6)

So X played on 2 as his first move. If O played on 4, it was a mistake: 2 4? 5! 8 3 (double threat 1/7). Thus O played on 1, and X played on 7. But then O should have played on 8 (blocking the double threat) or 5 (creating a threat on his own) instead of 4, so O's second move was also a mistake. (Note that 9 doesn't work: 2 1 7 9? 5! (double threat 3/8).)

Good analysis, Ivan. I think the bottom line is that, in order to make the problem work-as-intended (so to speak), we must interpret the conditions as: both players know the basics of good strategy, like "If you have a winning move, make it; otherwise, if your opponent would have a winning move, block it." (otherwise, either player could have started) but not necessarily an advanced strategy or the ability to anticipate future moves (otherwise, neither player could have started).

Peter Byers - 7 years, 2 months ago

From what I understand, O's second move was a clear strategic mistake. We have to assume that. If not this, then X made a similar mistake. Once either of these assumptions is made, either solution becomes possible, hence indeterminate. It begins to look like the players lack sense, and even though they're looking to win, they're somewhat daft. Now once that is known, who's to say they know that the winning move is staring them in the face? Forgive me if this sounds rude.

Revant Chopra - 7 years ago
Mayank Holmes
Apr 8, 2014

if X was the last move then why wasn't X drawn on the middle square to stop O from completing its triplet........ there seems no conceivable motive behind this! on the other hand if O was the last move and if we omit the 9th square ( 3rd row 3rd column), it is apparent that X was sure to win! we call this situation a DOUBLE CROSS in common language. now there remain no grounds for doubt that O was the last move and hence X will be the next and also the victorious move!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...