How many solutions are there if you draw 14 Crosses in a 6x6 Grid?

492 Views Asked by At

I found this Problem on Puzzling 14 crosses in a 6 by 6 grid and I really started thinking about it. The Problem goes as follows:

Draw 14 crosses in a 6x6 grid so that there is an even number of crosses in each horizontal and vertical row.

I puzzled for a while and even found a solution, but then I wondered how many solutions are there to this puzzle. And I asked me this questions?

1) How many solutions are there to put 14 crosses to a 6x6 grid without the even number of crosses limitation? The solution is: $$\frac{36!}{14! \times 22!} = 3'796'297'200$$

But I could not solve it with the limitations, because I do not know how to approach the following questions.

2) How many solutions are there, if the number of crosses in a row can be zero?

3) How many solutions are there, if the number of crosses in a row cannot be zero?

4) How many solutions are there, if it has to be symmetrical (reflectional or rotational)?

5) How many solutions are there, if it has to be symmetrical (reflectional or rotational) and the number of crosses in a row cannot be zero?

Here you can play around if you want 6x6 Grid

1

There are 1 best solutions below

0
On BEST ANSWER

This is probably a bit too hard to do by hand. Probably the best thing to do here is to use a computer. 3 billion possibilities is something a computer program can certainly handle.

Still, if you want top try and do this by hand, version 5 is probably the easiest, and maybe even the only 'feasible' one, to answer.

Here is a start with that:

First, not having any empty rows or columns means that you have one row and one column with $4$ crosses, and the other five rows having $2$ crosses.

Second, because there is exactly one row/column with $4$ crosses and there being an even number of rows and columns, symmetry by horizontal or vertical reflection is impossible. Symmetry by 180 degree rotation is impossible for the same reason, and therefore symmetry by 90 degree rotation is ruled out as well. You can, however, get symmetry by reflection along the diagonals, e.g.

\begin{array}{|c|c|c|c|c|c|} \hline X&&&X&&\\ \hline &&X&&&X\\ \hline &X&X&X&X&\\ \hline X&&X&&&\\ \hline &&X&&X&\\ \hline &X&&&&X\\ \hline \end{array}

This is the only kind of symmetry you can have, though. Also, note that you cannot have symmetry along one diagonal and symmetry along the other diagonal at the same time, since if you have, you would have 180 rotational symmetry, which we already established you can't have. This means that we only need to calculate the number of boards using symmetry along one diagonal, and multiply by two to get the total number of ways; there will be no double-counting there. So, let's just consider the boards with the top-left to bottom-right diagonal as the diagonal of symmetry.

Third, we need an even number of crosses on the diagonal of symmetry, i.e. $0$, $2$, $4$, or $6$, otherwise we would not get symmetry.

Now, I'll do the cases of $6$ and $4$ (the easiest ones), and maybe you can likewise figure out the cases of $2$ and $0$ ... which will be more work .. but I think just about doable by hand.

So, let's first consider the cases of having $6$ crosses along the diagonal:

\begin{array}{|c|c|c|c|c|c|} \hline X&&&&&\\ \hline &X&&&&\\ \hline &&X&&&\\ \hline &&&X&&\\ \hline &&&&X&\\ \hline &&&&&X\\ \hline \end{array}

We need one row with $4$ crosses, which by diagonal symmetry gives us our one column with $4$ crosses as well:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&X&-&-\\ \hline X&X&&&&\\ \hline X&&X&&&\\ \hline X&&&X&&\\ \hline -&&&&X&\\ \hline -&&&&&X\\ \hline \end{array}

Of course, we could have chosen any of the $6$ rows here, and we could have chosen any $3$ out of the $5$ remaining columns to put the $3$ extra crosses, so there are $6 \cdot {5 \choose 3} = 60$ ways to do this. Notice, though, that once we have placed those $3$ crosses, the corresponding rows and columns have the two crosses that they should have, and so we immediately get:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&X&-&-\\ \hline X&X&-&-&-&-\\ \hline X&-&X&-&-&-\\ \hline X&-&-&X&-&-\\ \hline -&-&-&-&X&\\ \hline -&-&-&-&&X\\ \hline \end{array}

And thus the last two crosses are forced:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&X&-&-\\ \hline X&X&-&-&-&-\\ \hline X&-&X&-&-&-\\ \hline X&-&-&X&-&-\\ \hline -&-&-&-&X&X\\ \hline -&-&-&-&X&X\\ \hline \end{array}

OK, so you have $60$ boards with a top-left to right-bottoom diagonal symmetry with $6$ crosses along that diagonal.

Now let's do the case of having $4$ crosses along the diagonal:

\begin{array}{|c|c|c|c|c|c|} \hline X&&&&&\\ \hline &X&&&&\\ \hline &&X&&&\\ \hline &&&X&&\\ \hline &&&&-&\\ \hline &&&&&-\\ \hline \end{array}

Of course, there are ${6 \choose 4}=15$ ways to place those $4$ crosses, so this is only one of those $15$. Now, again we need one row and column with $4$ crosses. There are two cases here:

  1. First, consider the case that this is a row/column that has a cross on its diagonal, i.e. it needs $3$ more crosses. There are several ways to place those crosses relative to the existing crosses:

1A. We could try and have all the crosses 'match up', i.e:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&X&-&-\\ \hline X&X&&&&\\ \hline X&&X&&&\\ \hline X&&&X&&\\ \hline -&&&&-&\\ \hline -&&&&&-\\ \hline \end{array}

But now all those rows and columns are done, i.e. we get:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&X&-&-\\ \hline X&X&-&-&-&-\\ \hline X&-&X&-&-&-\\ \hline X&-&-&X&-&-\\ \hline -&-&-&-&-&\\ \hline -&-&-&-&&-\\ \hline \end{array}

and so this doesn't work.

1B. For the row that needs three extra crosses (one out of $4$ rows), let's put those on two out of the three columns (i.e. there are ${3 \choose 2}=3$ possibilities here) that have a cross on their diagonal, i.e.:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&-&X&-\\ \hline X&X&-&-&-&-\\ \hline X&-&X&-&-&-\\ \hline -&-&-&X&&\\ \hline X&-&-&&-&\\ \hline -&-&-&&&-\\ \hline \end{array}

This means that there is one row that still has no crosses, and thus the rest of the crosses are forced:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&X&-&X&-\\ \hline X&X&-&-&-&-\\ \hline X&-&X&-&-&-\\ \hline -&-&-&X&-&X\\ \hline X&-&-&-&-&X\\ \hline -&-&-&X&X&-\\ \hline \end{array}

1C. Finally, we can have one of the three crosses placed in a column with a cross on its diagonal (or, put differently, we can put a cross in both columns that do not have a cross in their diagoanl, leaving one to put in any of the three others), which can be done in ${3 \choose 1} = 3$ ways:

\begin{array}{|c|c|c|c|c|c|} \hline X&X&-&-&X&X\\ \hline X&X&-&-&-&-\\ \hline -&-&X&&&\\ \hline -&-&&X&&\\ \hline X&-&&&-&\\ \hline X&-&&&&-\\ \hline \end{array}

OK, so now there are $4$ rows left with $1$ cross each, and three columns to choose from for each row. However, placing a cross in any of those $3$ columns in any of the rows will force the rest of the crosses, and so there are $3$ ways to finish up this pattern, giving a total of $9$ possibilitieand with $4$ rows to choose from to put the $3$ extra crosses, that's $36$ possibilities for 1C

  1. It is also possible for the row with the $4$ crosses to be one (of two) that does not have a cross on its own diagonal. Now there are two ways we can try to do this:

2A. All $4$ crosses are placed in columns that have a cross on its diagonal:

\begin{array}{|c|c|c|c|c|c|} \hline X&-&-&-&X&-\\ \hline -&X&-&-&X&\\ \hline -&-&X&-&X&-\\ \hline -&-&-&X&X&-\\ \hline X&X&X&X&-&-\\ \hline -&-&-&-&-&-\\ \hline \end{array}

... which obviously doesn't work out.

2B. Three out of $4$ (which forces the placement of the fourth, so $4$ options here):

\begin{array}{|c|c|c|c|c|c|} \hline X&-&-&-&X&-\\ \hline -&X&-&-&X&\\ \hline -&-&X&-&X&-\\ \hline -&-&-&X&-&\\ \hline X&X&X&-&-&X\\ \hline -&-&-&&X&-\\ \hline \end{array}

this will force the last crosses:

\begin{array}{|c|c|c|c|c|c|} \hline X&-&-&-&X&-\\ \hline -&X&-&-&X&\\ \hline -&-&X&-&X&-\\ \hline -&-&-&X&-&X\\ \hline X&X&X&-&-&X\\ \hline -&-&-&X&X&-\\ \hline \end{array}

So, in total we have $15 \cdot (12+36+8)=840$ possible boards with $4$ crosses on the left-top to bopttom-right diagonal of symmetry.

OK, I will leave the case of having $2$ or $0$ crosses on the diagonal of symmetry to you. Like I said, you will get more cases to consider here, but I think it will still be doable by hand on paper; just make sure you keep good organization of all the different cases. But, the main idea is to just pick one of the rows to have the $4$ crosses (or whatever other property you need), and then multiply at the end by the number of ways you could have picked those rows, since by symmetry working it out for 1 case will end up in exactly the same result as working it out for some other choice of row.

Once you have figured out the number of possibilities for the $2$ and $0$ cross on the left-top to bottom-right diagonal of symmetry, add those to the $60$ and $240$ possibilities for having $6$ and $4$ crosses, and finally multiply that total by two to also account for the top-right to bottom-left diagonal of symmetry, and you will have your answer for version 5 of your questions.

Good luck!