3
$\begingroup$

I am currently studying the problem of combination. And when I am doing an exercise, I saw the following question:

There is a 3 x 3 grid, and for each cells in the grid, two players take turn to fill each of them with either a cross or a circle (each player picks either a cross or circle, and stays consistent throughout the activity). How many ways the grid can be filled until all the cells are full?

The given answer is 252, but why?

Should the answer be 2 to the power of 9? At least if we consider the grid as a binary string of length 9, the answer should be 2 to the power of 9 ......

$\endgroup$
0

2 Answers 2

4
$\begingroup$

It is not $2^9$ because the two players take turns, and so there must be 4 crosses and 5 circles, or 5 crosses and 4 circles. Thus, we must pick 4 of the 9 total squares to be crosses, or 4 of the total circles squares to be circles, so the answer is $2\cdot\binom94=2\cdot\frac{9\cdot8\cdot7\cdot6}{4\cdot3\cdot2\cdot1}=2\cdot126=252$.

$\endgroup$
1
$\begingroup$

Note, for a start, that WLOG the first and second player both have the same number of strategies. This means there are really $252/2 = 126$ ways of filling the grid if we disregard who gets crosses and who gets circles.

Then, how many ways are there to pick $5$ of the unique cells (note that this implicitly also picks $4$ cells for the other symbol)? As it turns out, that's ${9 \choose 5} = 126$. After all, the order in which you pick these doesn't really matter.

So what you get is ${9 \choose 5} \cdot 2 = 252$, in the end.

$\endgroup$
2
  • 2
    $\begingroup$ You meant $\binom{9}{5} \cdot 2 = \color{red}{252}$. $\endgroup$ Oct 9, 2015 at 13:00
  • $\begingroup$ @N.F.Taussig oops. $\endgroup$
    – Newb
    Oct 9, 2015 at 20:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .