Maths Olympiad Prep

Library / /908 of 1394

, 2019

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

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 77?

Solution

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 11 in its rightmost digit, exactly one number with a 11 in the second digit from the right, and exactly one number with a 11 in the third digit from the right. Thus, consider the following operation: start with every unit square filled with the number 00. Add 11 to three unit squares, no two in the same row or column. Then add 22 to three unit squares, no two in the same row or column. Finally, add 44 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 33 by 33 square. Hence the answer is 216216.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.