What if all boxes are destroyed?

Both conditions are satisfied if all boxes are destroyed.

As it looks to me, condition 2 is violated.

If all boxes are destroyed, then there is no box that is neither destroyed nor coloured, so condition 2 is satisfied.

I understand now. Thanks.

$bump ....$

Anyone?

Bump....

Tintarn wrote: Given a positive integer $n$, Susann fills a square of $n \times n$ 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 We colour the boxes using the following algorithm: In every step we look at the set $S$ of uncoloured boxes $s$ not satisfying condition $2)$. If $S=\emptyset$ we stop. Otherwise denote for every row $r$ containing an box from $S$ the maximal number in a box from $S$ in this row with $a_r$ and denote the minimum of the $a_r$ with $a$. We colour the box from the row $r$ with $a_r=a$ with number $a$ in it. If there is another red box in the same coloum we remove the colour from it. Then we repeat this step. It remains to show that this algorithm terminates and returns a valid colouring. First, we claim that for a row $r$ containing a red box every box in $r$ satisfies condition $2)$. In the step in which a box in the row with number $a$ is couloured, for all bigger numbers in the row, there is a smaller number in their coloum, by the choice of the newly coloured box. The colour from a red box in the same coloum can only be removed, if a box in this coloum with an even smaller number in it get coloured. So every box in $r$ satisfies $2)$ if one box in it is coloured. In every step a box not satisfying $2)$ gets coloured, so there can never be two coloured boxes in the same row. In every step the algorithm directly removes in the same coloum of the newly coloured box the colour from every other box. So after every step there are no two red boxes in the same coloum and condition $1)$ is satisfied. The sum of the numbers in the red boxes decreases every step until the number of red boxes incrases. So the algorithm must terminate. When this happens the condition $2)$ is satisfied for every box. So the colouring is valid.