Filling a square with integers and colouring some of them
Source: Germany 2018, Problem 3
June 17, 2018
combinatoricsColoringInteger
Problem Statement
Given a positive integer , Susann fills a square of boxes. In each box she inscribes an integer, taking care that each row and each column contains distinct numbers. After this an imp appears and destroys some of the boxes.
Show that Susann can choose some of the remaining boxes and colour them red, satisfying the following two conditions:
1) There are no two red boxes in the same column or in the same row.
2) For each box which is neither destroyed nor coloured, there is a red box with a larger number in the same row or a red box with a smaller number in the same column.
Proposed by Christian Reiher