Maths Olympiad Prep

Library / /548 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

How many ways can one fill a 3×33 \times 3 square grid with nonnegative integers such that no nonzero integer appears more than once in the same row or column and the sum of the numbers in every row and column equals 7 ?

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

Solution

In what ways could we potentially fill a single row? The only possibilities are if it contains the numbers (0,0,7)(0,0,7) or (0,1,6)(0,1,6) or (0,2,5)(0,2,5) or (0,3,4)(0,3,4) or (1,2,4)(1,2,4). Notice that if we write these numbers in binary, in any choices for how to fill the row, there will be exactly one number with a 1 in its rightmost digit, exactly one number with a 1 in the second digit from the right, and exactly exactly one number with a 1 in the third digit from the right. Thus, consider the following operation: start with every unit square filled with the number 0 . Add 1 to three unit squares, no two in the same row or column. Then add 2 to three unit squares, no two in the same row or column. Finally, add 4 to three unit squares, no two in the same row or column. There are clearly 63=2166^{3}=216 ways to perform this operation and every such operation results in a unique, suitably filled-in 3 by 3 square. Hence the answer is 216.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.