Problem

Source: Romanian Junior TST Day 4 Problem 2 2008

Tags: geometry, geometric transformation, reflection, inequalities, induction, rectangle, combinatorics proposed



Let $ m,n$ be two natural nonzero numbers and sets $ A = \{ 1,2,...,n\}, B = \{1,2,...,m\}$. We say that subset $ S$ of Cartesian product $ A \times B$ has property $ (j)$ if $ (a - x)(b - y)\le 0$ for each pairs $ (a,b),(x,y) \in S$. Prove that every set $ S$ with propery $ (j)$ has at most $ m + n - 1$ elements. The statement was edited, in order to reflect the actual problem asked. The sign of the inequality was inadvertently reversed into $ (a - x)(b - y)\ge 0$, and that accounts for the following two posts.