0
$\begingroup$

The following figure shows a $3^2\times 3^2$ grid divided into $3^2$ subgrids of size $3\times 3$. This grid has $81$ cells, $9$ in each subgrid.

Grid

Now, consider an $n^2\times n^2$ grid divided into $n^2$ subgrids of size $n\times n$.

Find the number of ways in which we can select $n^2$ cells from this grid such that there are exactly one cell coming from each subgrid, one from each row and one from each column.

I could not advanced notably, so I am not posting this. Please give me the idea to solve this.

$\endgroup$
3
  • $\begingroup$ So we have to select 9 cells from $n^2$ following that rules, not $n^2$ from $n^2$, isn't it? $\endgroup$ Sep 8, 2015 at 18:01
  • $\begingroup$ @mkspk, it's $n^2$ out of $n^2\times n^2$ grids, I need the general form. $\endgroup$
    – user249332
    Sep 8, 2015 at 18:05
  • $\begingroup$ I posed this as The American Mathematical Monthly Problem 11573, and the solution appeared in the April 2013 issue. The count is $n!^{2n}$. $\endgroup$
    – RobPratt
    Apr 11, 2020 at 18:57

1 Answer 1

1
$\begingroup$

Hint: I will show you how to handle the case $n = 3$, then you can generalize from there.

Choose the elements by picking one element from each column, starting from the left. For the first column, you can first choose with subgrid to take the number from. There are $3$ possibilities for that. In each subgrid you have $3$ choices for the number, which makes $3 \cdot 3$ possible choices for the first column.

For the second column, you can choose from $2$ different subgrids and in each subgrid you have again $3$ possibilites, for a total of $2 \cdot 3$ possibilities. For the last column, you have only $1$ choice for the subgrid in which you have then $3$ choices for the cell, which makes $1 \cdot 3$ possibilities.

For the fourth column, you can again choose any subgrid, but within each subgrid you have only $2$ possible choices for the cell, leaving you with $3 \cdot 2$ possibilities. For the fifth column you have $2$ choices for the subgrid and $2$ for the cell, which means you have $2 \cdot 2$ possibilities. For the sixth column you have $1$ choice for the subgrid and $2$ choices for the cell, leaving you with $1 \cdot 2$ possibilities.

Doing the same thing for the last three columns yields the following number of total possibilites:

$$((3 \cdot 3) (2 \cdot 3) (1 \cdot 3)) \cdot ((3 \cdot 2)(2 \cdot 2)(1 \cdot 2)) \cdot ((3 \cdot 1)(2 \cdot 1)(1 \cdot 1))$$

$\endgroup$
0