Putnam 1959/B4 solution

20th Putnam 1959

Problem B4

A is the 5 x 5 array:


11 17 25 19 16

24 10 13 15  3

12  5 14  2 18

23  4  1  8 22

 6 20  7 21  9

Pick 5 elements, one from each row and column, whose minimum is as large as possible (and prove it so).

Solution

Answer: 25, 23, 20, 18, 15.

We can only pick one of 16, 17, 19, 25; only one of 23, 24; only one of 18, 22; and only one of 20, 21. That only gives 4 elements, so the minimum cannot be larger than 15. The answer shows that 15 can be achieved.

20th Putnam 1959