0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ You seem to be quite stuck since you thought that it was worth it to get an account here and post your problem, so there must be things you have tried or ideas you don't know how to follow up. Tell us about them! Edit your post and add those things in there. It will make it a lot easier for us to give you an answer that we think you will understand and actually learn something from. $\endgroup$ – Arthur Mar 12 '18 at 20:53
  • $\begingroup$ @arthur I will! Thank you very much for your advice, Mr. Arthur! $\endgroup$ – starsinajar Mar 12 '18 at 22:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks a lot for your super quick reply! Now I understand how to solve the problem using your method. Thanks again! $\endgroup$ – starsinajar Mar 12 '18 at 22:52
  • $\begingroup$ I assume you meant to say the placing in the lower left box is fixed since you have already placed an $X$ in each of the other boxes. $\endgroup$ – N. F. Taussig Mar 13 '18 at 1:14
  • $\begingroup$ @N.F.Taussig: Actually I meant for the third $X$ to go in the lower left, so you found the wrong mistake. I'll fix. Thanks. $\endgroup$ – Ross Millikan Mar 13 '18 at 1:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you so much for your super fast reply! I learned a lot from it. I have just one question about your answer: Why do we divide specifically by $4!$ at the end? $\endgroup$ – starsinajar Mar 12 '18 at 22:39
  • $\begingroup$ @starsinajar because that is the number of ways to distinguish the $X$'s. That is, if you have four $X$'s, then there are $4!$ ways to label them as $X_1$, $X_2$, $X_3$, and $X_4$. And that is, in effect, what I did when calculating the $384$ possibilities: first I placed $X_1$, then $X_2$, etc. But since in the end all the $X$'s are the same, we have to 'un-distinguish' them, i.e. Divide by $4!$ $\endgroup$ – Bram28 Mar 13 '18 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.