perplexus.info :: Games : Tic Tac Toe

Tic Tac Toe (Posted on 2002-09-27)

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."

Why?

(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
Puzzle Thoughts	K Sengupta	2023-07-18 23:49:31
an itemized result	Ady TZIDON	2015-07-25 02:30:52
another method	Dan Porter	2004-01-15 04:45:03
re(2): Actual Counts	Jim Lyon	2002-10-02 11:55:36
re: Actual Counts	levik	2002-09-30 11:07:16
Actual Counts	Jim Lyon	2002-09-30 10:41:47
re(3): Solution	friedlinguini	2002-09-29 10:39:21
re(2): Solution	levik	2002-09-29 05:56:14
re: Solution	TomM	2002-09-29 01:55:35
Solution	Jacob Fugal	2002-09-28 08:21:43
re(2): One reason	friedlinguini	2002-09-27 13:23:55
re: One reason	Jim Lyon	2002-09-27 13:13:38
One reason	friedlinguini	2002-09-27 12:21:03

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

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

Chatterbox:


perplexus dot info