Saturday problem of combinatorics

There are $8$ odd and $8$ even numbers $\Rightarrow$ two rows have three odd numbers and two only one.

First select which rows have three odd numbers, this is $\binom{4}{2}=6$

For the rows with three odd numbers are four arrangements, and each arrangement only can be combined with one of the other three, $4\times 3=12$ ways:

The rows with one odd number are defined by the last step and without lose of generality we only have to arrange two odd number as next figure shows:

Finally, permute odd an even numbers. $8!\times8!$

$\therefore$ the number of arrangements is $6\times12\times2\times 8!\times 8!=144\times (2^{3}!)^2 \Rightarrow 3^a\times2^b+8!=\boxed{40464}$

Lemma 1: There are two rows with three odd numbers, and the other two rows have only one odd number.

Proof: A row has $4$ numbers, therefore there are at most $4$ odd numbers. However, the condition is that each row has an odd sum. Therefore, the number of odd numbers are also odd. Therefore, each row has either $1$ odd number or $3$ odd numbers. Let the number of rows with $1$ odd number be $a$ and the number of rows with $3$ odd numbers be $b$ . Since there are a total of $8$ odd numbers available from $1$ to $16$ : $a\times1+b\times3=8$ Also, there are only $4$ rows, so: $a+b=4$ Solving the equations give us: $\begin{cases}a=2\\b=2\end{cases}$ $\square$

Lemma 2: There are two columns with three odd numbers, and the other two columns have only one odd number.

Proof: This follows from a similar argument with lemma 1.

$\square$

Lemma 3: A "hole" refers to the even number in the rows with 3 odd numbers. Then, the two rows with 3 odd numbers cannot have holes belonging to the same column.

Proof: Assume the opposite.

Then, there are now three columns with two odd numbers. There can be no place to add the remaining odd numbers to these columns such that two rows have only one odd number.

Therefore the result follows.

$\square$

THEREFORE:

• $\dbinom42$ to choose two rows that have three odd numbers.
• $4$ for the hole in the first row containing three odd numbers.
• $3$ for the hole in the second row containing three odd numbers.
• $2$ for the two possibilities for the remaining odd entries.
• $8!$ for arranging the $8$ odd numbers.
• $8!$ for arranging the $8$ even numbers.

And the total number of arrangements = $\dbinom42\times4\times3\times2\times8!\times8!$ = $2^4\times3^2\times8!^2$ .