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

Home > Games
Tic Tac Toe (Posted on 2002-09-27) Difficulty: 3 of 5
A computer science teacher poses his students a problem.

"I want you write a computer program that plays tic-tac-toe legally and runs through ALL the possible combinations of the game, and finds out the total."

The students settle down to work..

An hour later, a student gets up and proclaims "I've got it! The number of possible combinations in a game is 344,242."

At which point another student quickly replies, "I haven't finished yet, but I'm sure Fred made a mistake in his program."


(Tic Tac Toe = Noughts and Crosses)

  Submitted by Cheradenine    
Rating: 3.5455 (11 votes)
Solution: (Hide)
The total combinations can be partitioned into first move groups. Positions starting at corners and sides are indistinguishable. This means that each of
them (4) must yield the same number of combinations.

Total = 4*(Corner) + 4*(Side) + Middle

In Middle games, the second move is inevitably a corner or side. Because the middle mark is in the middle, symmetry still applies, as in the previous calculation.

T = 4C + 4S + (4C' + 4S')
T = 4(C + S + C' + S')

The number given by the first student is not divisible by 4. So even though the second student does not know the exact value, he knows fredīs suggestion is incorrect.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Hints/Tipsan itemized resultAdy TZIDON2015-07-25 02:30:52
another methodDan Porter2004-01-15 04:45:03
re(2): Actual CountsJim Lyon2002-10-02 11:55:36
re: Actual Countslevik2002-09-30 11:07:16
Actual CountsJim Lyon2002-09-30 10:41:47
re(3): Solutionfriedlinguini2002-09-29 10:39:21
re(2): Solutionlevik2002-09-29 05:56:14
re: SolutionTomM2002-09-29 01:55:35
SolutionSolutionJacob Fugal2002-09-28 08:21:43
re(2): One reasonfriedlinguini2002-09-27 13:23:55
Some Thoughtsre: One reasonJim Lyon2002-09-27 13:13:38
One reasonfriedlinguini2002-09-27 12:21:03
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information