# Problem 6. (3 points)

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

## Solution:

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

Let's consider several cases:

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

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