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)
I started by looking for the number of winning games at the fith move.
There are 8 way to win. 3 vertical, 3 horizontal and 2 diaganal.
There are 6 ways to place 3 objexts in a row. 123, 132, 213, 231, 312, 321
6*8=48 combonations for the first player.
The second player placed 2 objects in 6 possible locations for 6*5=30 combotaions.
Total winnig combos after 5 moves is 48*30=1440.
This by the way is the same as the actual count by Jim Lyon. I'm guessing he coded correctly.
By removing just these winning combos you get a number less than 344242.
(9*8*7*6*5-1440)*4*3*2+1440=329760
Edited on January 15, 2004, 4:52 am
Edited on January 15, 2004, 5:11 am
another method
