1
$\begingroup$

Given a $2 \times 4$ grid, I need to find in how many distinct ways one can fill the grid with $1,2,\dots,8$ such that on each row and column there are an even number of even numbers.

Repetitions are allowed. For example, the all-ones grid would be admissible.

Update :

What's the number of grids if repetitions are not allowed?

$\endgroup$
7
  • 2
    $\begingroup$ Your progress on trying to solve it would be really appreciated. We can help you from where you got stuck. $\endgroup$ – user79161 Mar 6 at 10:02
  • $\begingroup$ Actually, I have no idea how to solve it :)) $\endgroup$ – andrei81 Mar 6 at 10:24
  • 3
    $\begingroup$ Do you mean all the digits between $1$ and $8$ are to be used, or may digits be repeated? $\endgroup$ – N. F. Taussig Mar 6 at 10:24
  • 1
    $\begingroup$ Think about the $\{0,1\}$-matrices of this kind. $\endgroup$ – Christian Blatter Mar 6 at 14:13
  • 1
    $\begingroup$ Related: math.stackexchange.com/q/2294823/339790 $\endgroup$ – Rodrigo de Azevedo Mar 6 at 14:16
1
$\begingroup$

Let $o_r$ be the number of odd numbers in a row, $e_r$ be the total number of even numbers in a row, $o_c$ be the number of odd numbers in a column, $e_c$ be the total number of even numbers in a column.

Therefore

$2=o_r+e_r$

$4=o_c+e_c$

The number of even numbers is even so $e_r=\lbrace 0,2\rbrace$ and $e_c=\lbrace0,2,4\rbrace$

Plugging in these values in the above equations and solving for $o_r$ and $o_c$ give the results

$o_r=\lbrace 0,2\rbrace$ and $o_c=\lbrace0,2,4\rbrace$

Since there are an even number of odd numbers this is equivalent to saying that the sum of the values of a row or column must be even.

The sum of values for a column can be $\lbrace2,4,6,8,10,12,14,16\rbrace$

There are $32$ ways to fill in a column of numbers (from top to bottom)$\lbrace1,1\rbrace$,$\lbrace1,3\rbrace$,$\lbrace3,1\rbrace$,$\lbrace2,2\rbrace$,$\lbrace1,5\rbrace$,$\lbrace5,1\rbrace$,$\lbrace2,4\rbrace$,$\lbrace4,2\rbrace$,$\lbrace3,3\rbrace$,$\lbrace1,7\rbrace$,$\lbrace7,1\rbrace$,$\lbrace2,6\rbrace$,$\lbrace6,2\rbrace$,$\lbrace3,5\rbrace$,$\lbrace5,3\rbrace$,$\lbrace4,4\rbrace$,$\lbrace2,8\rbrace$,$\lbrace8,2\rbrace$,$\lbrace3,7\rbrace$,$\lbrace7,3\rbrace$,$\lbrace4,6\rbrace$,$\lbrace6,4\rbrace$,$\lbrace5,5\rbrace$,$\lbrace4,8\rbrace$,$\lbrace8,4\rbrace$,$\lbrace5,7\rbrace$,$\lbrace7,5\rbrace$,$\lbrace6,6\rbrace$,$\lbrace6,8\rbrace$,$\lbrace8,6\rbrace$,$\lbrace7,7\rbrace$,$\lbrace8,8\rbrace$

There are $16$ columns made of odd numbers and $16$ columns made of even numbers.

If three of four columns are filled in the parity of the fourth is forced. Below are all of the parity combinations:

$$\begin{array}{|c|c|c|c|} \hline Selected&Selected&Selected&Forced\\ \hline odd&odd&odd&odd\\ \hline odd&odd&even&even\\ \hline odd&even&odd&even\\ \hline odd&even&even&odd\\ \hline even&odd&odd&even\\ \hline even&odd&even&odd\\ \hline even&even&odd&odd\\ \hline even&even&even&even\\ \hline \end{array}$$

The first three columns there are $32$ choices each, then the fourth column is a forced parity with $16$ choices. This is $32^3×16=524288$ ways of filling in the $2×4$ grid.

$\endgroup$

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