Consider the game of tic-tac-toe, where players alternately move. Player 1 (who moves first) puts Xs, and player 2 puts Os, on the 3 3 board. Normally in this game, we stop when someone has three in a row. However, now suppose that we always continue all the way until the board is full. So the players move in the sequence 1, 2, 1, 2, 1, 2, 1, 2, 1.

1- How many possible final states of the board are there? (Note: if one state can be obtained from another by rotating or flipping the board, this does not mean that these states are the same. But the order in which Os and Xs were put on the board does not matter, as long as the board looks the same at the end. I.e., if the board looks the same, it's the same state.)

Answer: There are .............................. possible final states.

2- How many different possibilities are there for the full history of the game until the end? I.e., how many different sequences of play until the end are there? If two sequences of play end up with the same final state, but the Xs and Os were put in in a different order, these are two different sequences. (Hint: One might represent a sequence by a final state of the board, plus, for every space on the board, the timefrom 1 through 9at which this space was filled.)

Answer: There are ........................................ posibilities of the full history of the game (each is a sequence of moves from the initial state to a final state where the game ends.)

3- Now suppose there is a third player who puts Zs. Players move in the sequence 1, 2, 3, 1, 2, 3, 1, 2, 3. Answer question a again now that there is a third player. (Hint: consider the number of ways there are to first choose w elements out of a set of n elements, and to then choose v elements out of those w. The number of ways is nCw * wCv, where nCk denotes a k-combination, the number of ways to choose k distinct elements out of n elements.

4- Answer question 2 again now that there is a third player.

Answer: There are .............................. possibilities of the full history of the game