Maths Olympiad Prep

Library / /26 of 42

Combinatorics Difficulty 6.0 National olympiad Prove it Ireland

The numbers 11 to 99 are arranged in a 3×33 \times 3 square. Such a square is row-balanced if the sum of the numbers in each row is the same.
How many of the 9!9! possible squares are row-balanced?

Solution

The target row sum is 910/23=159 \cdot 10/2 \cdot 3 = 15. We first note that the small numbers 11, 22, and 33 must be in separate rows since if two of them were in the same row, the sum would be too small: we would get at most 2+3+9=142 + 3 + 9 = 14. In a similar fashion, the large numbers 77, 88, and 99 must be in separate rows. It follows that each row has one small and one large number.

Multiples of 33 cannot all be in the same row (since 3+6+9>153+6+9 > 15), nor can a row have exactly two multiples of 33 (the sum would not be divisible by 33). Thus, each row has exactly one multiple of 33. It follows that each row has numbers in all mod-33 congruence classes.

Given these constraints and ignoring the order of the elements, there are just two possibilities for the row containing 11 ({1,5,9}\{1, 5, 9\} or {1,6,8}\{1, 6, 8\}) and for the row containing 22 ({2,4,9}\{2, 4, 9\} or {2,6,7}\{2, 6, 7\}). Because of overlapping elements, each possible row containing 11 is compatible with only one possible row containing 22. Once these two rows are chosen, the final row is also known, so there are only two ways of allocating the elements to rows.

These three rows can be put in any order, e.g. first the row with 11, then the one with 22, etc., giving 3!=63! = 6 possible re-orderings of rows. Internal to each row, we can re-order the elements in 3!3! ways. Thus, the total number of row-balanced squares is 642=25346^4 \cdot 2 = 2^5 \cdot 3^4.

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 and solution reproduced as published; topic and difficulty added by this site.