Permutations of these blocks

74 Views Asked by At

You have 9 blocks with the following on their front; $(1,9), (2,8), (3,7), (4,6),(5,5),(6,4),(7,3),(8,2),(9,1)$

You have a $3\times3$ grid to fit the blocks in but the following rules must be followed;

Imagine each block is of the form $(x,y)$

(1) Each row has to have increasing $x$ values from left to right

(2) Each column has to have increasing $y$ values from bottom to top

How many different permutations are there for filling this grid?


So far I have managed 2 different ones and know that (9,1) must be in bottom right in all permutations and (1,9) must always be top left.

Is there any more permutations?

1

There are 1 best solutions below

0
On BEST ANSWER

There are many more. I assume the two you found are:

\begin{array}{|c|c|c|} \hline (1,9) & (2,8) & (3,7)\\ \hline (4,6) & (5,5) & (6,4)\\ \hline (7,3) & (8,2) & (9,1)\\ \hline \end{array}

\begin{array}{|c|c|c|} \hline (1,9) & (4,6) & (7,3)\\ \hline (2,8) & (5,5) & (8,2)\\ \hline (3,7) & (6,4) & (9,1)\\ \hline \end{array}

But here are just a few more:

\begin{array}{|c|c|c|} \hline (1,9) & (2,8) & (4,6)\\ \hline (3,7) & (5,5) & (6,4)\\ \hline (7,3) & (8,2) & (9,1)\\ \hline \end{array}

\begin{array}{|c|c|c|} \hline (1,9) & (3,7) & (5,5)\\ \hline (2,8) & (4,6) & (7,3)\\ \hline (6,4) & (8,2) & (9,1)\\ \hline \end{array}

To find them all, I suggest you start with the required $(1,9)$ in the top left (and yes, you might as well place the $(9,1)$ in the bottom right as well) then place $(2,8)$ (which can either go in middle of top row or middle of left column), then $(3,7)$ from each of those two possibilities, etc. You basically get what is called a search tree.

Now, using some symmetry considerations, you can save yourself a lot of work. For example, two possible ways (out of $4$ total) of placing the first couple of items are:

\begin{array}{|c|c|c|} \hline (1,9) & (2,8) & \\ \hline (3,7) & & \\ \hline & & (9,1)\\ \hline \end{array}

\begin{array}{|c|c|c|} \hline (1,9) & (3,7) & \\ \hline (2,8) & & \\ \hline & & (9,1)\\ \hline \end{array}

Clearly, the number of ways to place the remaining items will be exactly the same for each case, so just count them for one of those, and then double that.

Good luck!

P.s. The answer I get is:

42