Question 20
We are given a rectangular $m \times n$ chessboard with $m$ unit squares in each row and $n$ unit squares in each column. We are going to assign an integer to each unit square. A rectangle $R$ consisting of one or more unit squares is called a shelf if there is an integer $h$ satisfying the following two conditions:
1. The number in each unit square in $R$ is larger than $h$.
2. The number in a unit square out of $R$ sharing an edge or a point with $R$ is at most $h$.
(We assume that a shelf $R$ contains all interior unit squares in the rectangle.) What is the number of shelves if we assign integers to maximize the number of shelves?
1. The number in each unit square in $R$ is larger than $h$.
2. The number in a unit square out of $R$ sharing an edge or a point with $R$ is at most $h$.
(We assume that a shelf $R$ contains all interior unit squares in the rectangle.) What is the number of shelves if we assign integers to maximize the number of shelves?