Admissible sets of chessboard fields
Source: 51 Polish MO 2000 Second Round - Problem 3
April 23, 2018
combinatoricsChessboardgraph theoryPolandcombinatorics unsolved
Problem Statement
On fields of chessboard different integers have been arranged, one in each field. In each column, field with biggest number was colored in red. Set of fields of chessboard name admissible, if no two of that fields aren't in the same row and aren't in the same column. From all admissible sets, set with biggest sum of numbers in it's fields has been chosen. Prove that red field is in this set.