In how many ways can we to place an $X$ in four cells, such that there is exactly one $X$ in each row, column, and $2\times2$ outlined box?

131 Views Asked by At

I am a middle school student who would really appreciate it if somebody could explain how to solve this problem using simple terms. I saw this problem on this site and one other, but I am still unsure of how to get $384$ like the solution said here: Mini Sudoku -Critique of Solution-

In this circumstance -with $16$ available slots- there are $384$ possible combinations with over-counting.

And here is the problem:

Let's play mini-Sudoku!

We wish to place an $X$ in four cells, such that there is exactly one $X$ in each row, column, and $2\times2$ outlined box. For example:

enter image description here

In how many ways can we do this?

Terminology: A cell is one of small $1\times1$ spaces. A box is one of four outlined $2\times2$ group of cells. Please use this terminology so there is no ambiguity between you and your audience.

2

There are 2 best solutions below

3
On

You can put an $X$ in any one of the four cells in the upper left box. You then have two choices in the upper right box and two choices in the lower left box because of the row/column requirement. The placing in the lower right box is fixed, so there are $16$ different patterns. If you distinguish the order you place the $X$s this multiplies the number by $4!=24$. $16 \times 24=384$ as claimed.

2
On

They get the $384$ as follows:

Put the first $X$ anywhere on the board: $16$ possibilities there.

There are now two kinds of options for the second $X$:

A. Put it somewhere in the box that is diagonal from the box of the first cell. The first $X$ will not rule out any of the cells in that box, so there are $4$ options for placing the second $X$ in this 'diagonal' box. But then for the third, we have to put it in a box adjacent to the boxes of the first two, and a quick look at the diagram will reveal that the first two $X$'s will rule out every cell of that box except one, so the location is fixed. So, for the third $x$ you only have the option of choosing which box to put it in, so $2$ options for placing the third $X$. And that of course leaves exactly one option for the last $X$.

B. Have it go in on of the two boxes that are adjacent to the box that the first $X$ is in: there are two such boxes, and for each box, two cells will be ruled out due to the first $X$, and so there are two available cells left. So, $2 \cdot 2 = 4$ options for placing the second $X$ in an 'adjacent' box. The third $X$ can now be placed in either of the $2$ remaining boxes, and again a quick look at the diagram will reveal that each box still has $2$ available cells, so $2 \cdot 2 = 4$ options for the third $X$. And again, the last $X$ is now forced.

Total:

$$16\cdot (4 \cdot 2 + 4 \cdot 4) = 16 \cdot 24 =384$$

OK, but this is overcounting, since it distinguishes each of the $X$'s. So since the $X$'s are indistinguishable, you need to divide by $4!=24$, and so you are left with $16$ solutions.