MHB Problem #91: Counting Filled Tic-Tac-Toe Boards

  • Thread starter Thread starter Jameson
  • Start date Start date
AI Thread Summary
The discussion centers on calculating the total number of ways to fill a standard 3x3 tic-tac-toe board with X's and O's, assuming one piece plays first and there is always one more of that piece than the other. The focus is on counting completely filled boards without considering winning conditions or the various ways to reach those configurations. The problem simplifies to finding the combinations of X's and O's that can occupy the 9 spaces. Members have shared their solutions, with MarkFL being recognized for a correct answer. The conversation highlights the combinatorial nature of the problem in a straightforward manner.
Jameson
Insights Author
Gold Member
MHB
Messages
4,533
Reaction score
13
A standard tic-tac-toe board (or noughts and crosses) is a 3x3 grid, with 9 total spaces.

View attachment 1796
There are many different ways that the X's and O's can be placed on the board. If we ignore for now the rule that 3 pieces of one type in a row wins, how many ways can we fill the board completely? Assume that the same piece, X or O, plays first each time so you will always have 1 more of that piece than the other.

Note: The problem isn't to count moves that lead to a certain position. 1 filled board can be reached many ways. Just count the number of total filled boards. Also, don't worry about rotations or reflections for you guys who are more advanced.
--------------------
 

Attachments

  • Tic_tac_toe.png
    Tic_tac_toe.png
    2 KB · Views: 119
Physics news on Phys.org
Congratulations to the following members for their correct solutions:

1) MarkFL

Solution (from MarkFL):
This problem boils down to looking at how many ways to choose 9 things 5 at a time, or equivalently, how to choose 9 things 4 at a time. Thus, the number $N$ of distinct filled boards is given by:

$$N={9 \choose 5}={9 \choose 4}=\frac{9!}{4!\cdot5!}=\frac{9\cdot8\cdot7\cdot6}{4\cdot3\cdot2}=9\cdot7\cdot2=14(10-1)=140-14=126$$

Thus, we find there are 126 distinct filled boards.
 

Similar threads

Back
Top