Problem Set: Combinatorics

Problem 1963.1

Let p and q be integers greater than 1. There are pq chairs, arranged in p rows and q columns. Each chair is occupied by a student of different height. A teacher chooses the shortest student in each row; among these the tallest one is of height a. The teacher then chooses the tallest student in each column; among these the shortest one is of height b. Determine which of a < b, a = b and a > b are possible by an appropriate rearrangement of the seating of the students.

First Solution Let A be the tallest among the shortest student in each row, and B be the shortest among the tallest student in each column. Let A be in row i and B be in column j, and let C be the student of height c who is in row i and column j. Note that C may coincide with A or B. We have a ≤ c ≤ b, so that a > b is impossible. Put the tallest student in each column in the last row. Then the shortest student in this row qualifies as both A and B, yielding a = b. Now let her change seats with any other student in the same column. This move does not disqualify her as B, and she is still taller than the shortest student in each row except possibly her new row. We can certainly put a shorter student there, and then a < b.