Given the positive integer $m \geq 2$, $n \geq 3$. Define the following set $$S = \left\{(a, b) | a \in \{1, 2, \cdots, m\}, b \in \{1, 2, \cdots, n\} \right\}.$$Let $A$ be a subset of $S$. If there does not exist positive integers $x_1, x_2, y_1, y_2, y_3$ such that $x_1 < x_2, y_1 < y_2 < y_3$ and $$(x_1, y_1), (x_1, y_2), (x_1, y_3), (x_2, y_2) \in A.$$Determine the largest possible number of elements in $A$.
Problem
Source: CSMO Grade 10 Problem 8
Tags: combinatorics
06.08.2017 18:01
It's easier to interpret $S$ as cells on an $m \times n$ table, where the rows are numbered $1$ to $m$ from top to bottom, and columns are numbered $1$ to $n$ from left to right. A cell is shaded iff it's in $S$. The condition means there's no "T", formed by a shaded cell that has a shaded cell somewhere on its left, another shaded cell somewhere on its right, and a third shaded cell somewhere below it. Call a column $c$ numbered between $2$ and $n-1$ (inclusive) burned if there is some row $r$ and two additional columns $c_1, c_2$ with $c_1 < c < c_2$ such that $(r, c_1), (r, c), (r, c_2)$ are all shaded. In other words, there are already three cells forming a partial T, and any other cell below this row will complete the T. In addition, since $(r, c)$ is also shaded, if there's any other row $r' < r$ and two columns $c_1', c_2'$ with $c_1' < c < c_2'$ where $(r', c_1'), (r', c_2')$ are shaded, then they and $(r, c)$ also form three parts of a T, and so we cannot have $(r', c)$ shaded. This explains the name "burned"; it's very difficult to shade any other cell in this column. The most important thing is to note that a column cannot be burned twice: if column $c$ is burned by having $(r', c_1'), (r', c), (r', c_2)'$ and $(r, c_1), (r, c), (r, c_2)$ shaded with $r' < r$, then $(r', c_1), (r', c), (r', c_2), (r, c)$ form a T. Thus it's easy to give an upper bound now. For each row, ignore the leftmost and rightmost shaded cells; there are $2m$ of them. All the remaining cells burn their corresponding columns (because there are the leftmost and the rightmost shaded cells in their row to form parts of a T), so there are at most $n-2$ of them. This gives the answer $\boxed{2m+n-2}$, which can be easily achieved by shading the entire left column, right column, and bottom row to form a big "U" shape.