Maths Olympiad Prep

Library / /67 of 94

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Japan

A square with side length 33 is partitioned into a 3×33 \times 3 grid with 99 unit squares. In each of the 99 unit squares a distinct positive integer greater than or equal to 11 and less than or equal to 99 is inserted. For each of the 33 columns the second largest of the 33 numbers appearing on that column is marked. How many possible arrangements of the 99 integers are there if the second largest of the 33 marked numbers is 55?

Solution

First we show that if one of the marked numbers is 55, then 55 is the second largest of the three marked numbers. For this purpose, let us note that if 55 is marked for one of the columns, then there is exactly one number less than or equal to 44 in this column, and therefore, there must be a column which contains at least two numbers less than or equal to 44. For such a column the second largest number in it must be less than or equal to 44, so the number marked for that column must be less than or equal to 44. By the same reasoning we conclude that there must be a column for which the marked number is greater than or equal to 66. Thus 55 is the second largest of the marked numbers.
From the consideration made above, it is enough to find the number of arrangements of nine numbers having 55 as one of the marked numbers. There are 33 ways of choosing a column to contain 55, and for the chosen column containing 55 there are 424^2 ways of choosing other two numbers in that column, and there are 66 ways of permuting the chosen three numbers in that column. Finally, for each arrangement of three numbers in that column, there are 6!6! ways of arranging the remaining six numbers into the other two columns. Therefore, the total number of the desired arrangements is
3426(6!)=207360. 3 \cdot 4^2 \cdot 6 \cdot (6!) = 207360.

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.