Maths Olympiad Prep

Library / /33 of 46

, 2015

Number theory Difficulty 6.7 National Olympiad Prove it Japan

Suppose you want to distribute nine distinct integers greater than or equal to 11 and less than or equal to 99 into nine square boxes of a 3×33 \times 3 grid in such a way that the sums of the numbers on each row and each column are all multiples of 33. How many possible ways of distributing numbers are there to attain this goal? Regard two configurations, for which one can be obtained from rotating the other one or by flipping over the other one, to be distinct in counting the number of possible ways.

Solution

Let us replace every number nn distributed into a box in the grid by p=0,1,2p = 0, 1, 2 which satisfies the identity np(mod3)n \equiv p \pmod 3. The condition that the sum of the numbers on each row and on each column must be a multiple of 33 does not change after the replacement of the numbers nn by pp. Among the triples (a,b,c)(a, b, c) of integers lying in between (and including) 00 and 22, only (0,0,0)(0, 0, 0), (1,1,1)(1, 1, 1), (2,2,2)(2, 2, 2) and (0,1,2)(0, 1, 2) and its permutation of entries are the ones satisfying the requirement that the sum of the entries of the three numbers equals a multiple of 33. This means that only possible triplets to satisfy the requirement of the problem after the replacement of nn by pp are either the ones with all the same entries (such as (1,1,1)(1, 1, 1)) or the ones with all distinct entries (such as (0,1,2)(0, 1, 2)).

If we represent the remainders 00, 11, 22 by the letters AA, BB, CC (disregarding the order), we see that each of the letters AA, BB, CC can represent any of the three numbers 00, 11, 22 and the only possible placement of these letters that can satisfy the requirements of the problem must be one of the four placements indicated below:
Figure 1
Figure 2
Figure 3
Figure 4
For each of the placements shown above, there are 3!3! ways of associating 33 kinds of remainder to each of the three letters, and therefore, there are 43!=244 \cdot 3! = 24 possible ways of getting the distinct configurations after the replacement of numbers nn by remainders pp. Furthermore, since there are 33 possible ways of choosing integers nn for each of the possible remainders pp, there are (3!)3=216(3!)^3 = 216 ways of inserting integers for each of the 2424 possible configurations of the placements of remainders pp considered above.
Therefore, there are 24216=518424 \cdot 216 = 5184 ways of distributing numbers into the boxes of the grid, so as to satisfy the requirement of the problem.

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.