Maths Olympiad Prep

Library / /178 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

# Problem 6. (3 points)

In how many ways can natural numbers from 1 to 9 be arranged in a 3×33 \times 3 square table so that the sum of the numbers in each row and each column is odd? (Numbers can repeat)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Answer: 64653+94452+526 \cdot 4^{6} \cdot 5^{3}+9 \cdot 4^{4} \cdot 5^{2}+5^{2}.

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 321=63 \cdot 2 \cdot 1=6 ways to choose where these numbers are placed, 464^{6} ways to arrange the even numbers, and 535^{3} ways to arrange the odd numbers.
2) There are five odd numbers, i.e., they occupy one row and one column. There are 33=93 \cdot 3=9 ways to choose these row and column, 444^{4} ways to arrange the even numbers, and 555^{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 595^{9} ways.

In total, 64653+94452+596 \cdot 4^{6} \cdot 5^{3}+9 \cdot 4^{4} \cdot 5^{2}+5^{9}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.