# Problem 6. (3 points)

In how many ways can natural numbers from 1 to 7 be arranged in a $3 \times 3$ square table so that the sum of the numbers in each row and each column is odd? (Numbers can repeat)
Answer: $6 \cdot 3^{6} \cdot 4^{3}+9 \cdot 3^{4} \cdot 4^{5}+4^{9}$.

Solution:

In each row and each column of the table, there can be either one or three odd numbers. The total number of odd numbers is an odd number from 3 to 9.

Let's consider several cases:

1) There are a total of three odd numbers, one in each row and each column. We have $3 \cdot 2 \cdot 1=6$ ways to choose where these numbers are placed, $3^{6}$ ways to arrange the even numbers, and $4^{3}$ ways to arrange the odd numbers.
2) There are five odd numbers, i.e., they occupy one row and one column. There are $3 \cdot 3=9$ ways to choose these row and column, $3^{4}$ ways to arrange the even numbers, and $4^{5}$ ways to arrange the odd numbers.
3) Seven odd numbers are not possible, as this would mean there are only two even numbers. They cannot simultaneously be in the same row and the same column, which means some sums would be even.
4) All numbers are odd, in which case there are $4^{9}$ ways.

In total, $6 \cdot 3^{6} \cdot 4^{3}+9 \cdot 3^{4} \cdot 4^{5}+4^{9}$.