A square with side length is partitioned into a grid with unit squares. In each of the unit squares a distinct positive integer greater than or equal to and less than or equal to is inserted. For each of the columns the second largest of the numbers appearing on that column is marked. How many possible arrangements of the integers are there if the second largest of the marked numbers is ?
Solution
First we show that if one of the marked numbers is , then is the second largest of the three marked numbers. For this purpose, let us note that if is marked for one of the columns, then there is exactly one number less than or equal to in this column, and therefore, there must be a column which contains at least two numbers less than or equal to . For such a column the second largest number in it must be less than or equal to , so the number marked for that column must be less than or equal to . By the same reasoning we conclude that there must be a column for which the marked number is greater than or equal to . Thus 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 as one of the marked numbers. There are ways of choosing a column to contain , and for the chosen column containing there are ways of choosing other two numbers in that column, and there are ways of permuting the chosen three numbers in that column. Finally, for each arrangement of three numbers in that column, there are ways of arranging the remaining six numbers into the other two columns. Therefore, the total number of the desired arrangements is