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

 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.

 Subject Author Date 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

 Search: Search body:
Forums (0)