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.
Problem
Source: Romanian Junior TST Day 4 Problem 2 2008
Tags: geometry, geometric transformation, reflection, inequalities, induction, rectangle, combinatorics proposed
20.06.2008 17:26
We'll prove it by induction on $ n+m$. For $ n=m=1$ the statement is true. Let $ S$ be a set satisfying the condition and $ (a,b)\in S$ be any point other than $ (1,1)$ or $ (n,m)$. (If there are no such points, then $ S$ has at most 2 elements and so the statement is true for this $ S$). $ (a-x)(b-y)$ means that $ (x,y)\in S$ must be either in the rectangle $ (1,\ldots,a)\times(1,\ldots,b)$ or in the rectangle $ (a,\ldots,n)\times(b,\ldots,m)$. These rectangles are of sizes $ a \times b$, $ (n-a+1) \times (m-b+1)$. Since $ a+b<n+m$ and $ n-a+1+m-b+1<n+m$, the statement is true for both of these rectangles, so that there are at most $ a+b-1$ elements from $ S$ in the first one, and at most $ n-a+1+m-b+1-1$ elements from $ S$ in the second one. Hence, the total number of elements in $ S$ does not exceed $ (a+b-1)+(n-a+1+m-b+1-1)-1=n+m-1$. (note that we substracted 1 because $ (a,b)$ was so far counted twice as it's in the intersection). Wojtek
20.06.2008 18:16
Let $ S_k = \{(a, b) \in A \times B \mid a + b = k\}$. Then $ S_2 \cup S_3 \cup \cdots \cup S_{m + n} = A \times B$, and $ S$ can contain at most one element from each $ S_i$.
18.03.2014 17:36
In fact the property was misquoted; it was its exact reversal $ (a - x)(b - y)\le 0$ for any pairs $ (a,b),(x,y) \in S$. Funnily enough, the answer $m+n-1$ is the same!
13.04.2016 12:56
Here is a nice geometrical interpretation: Let $S=\{(a_i,b_i)|a_i\in A,b_i\in B\}$ be a set that has propriety $(j)$ and let $|S|=k$.Suppose that $a_1\le a_2\le...\le a_k$.From the hypothesis we know that $b_1\ge b_2\ge...\ge b_k$. Consider in the geometrical plane the set of points $\mathcal{P}=\{(a,b)|a\in A,b\in B\}$.By a lattice path we will refer to a path between two points $(a,b),(c,d)\in\mathcal{P},a\le c,b\ge d$ such that we move only to the right and\or down along the lattice grid starting from point $(a,b)$ and finishing at point $(c,d)$.It's pretty obvious that any lattice path from $(a,b)$ to $(c,d)$ has constant length(more precisely $c-a+b-d$). From $a_1\le a_2\le...\le a_k$ and $b_1\ge b_2\ge...\ge b_k$ we know that there is a lattice path $\mathcal{L}$ from $(a_1,b_1)$ to $(a_k,b_k)$ that passes through $(a_2,b_2),...,(a_{k-1},b_{k-1})$ and so $|\mathcal{L}|\ge k-1$($|\mathcal{L}|$ is the length of $\mathcal{L}$).But it's obvious that the longest lattice path between two points from $\mathcal{P}$ is the lattice path from $(1,m)$ to $(n,1)$,which has length $n-1+m-1=m+n-2$,so $$m+n-2\ge |\mathcal{L}|\ge k-1$$meaning that $k\le m+n-1$ or $|S|\le m+n-1$.This ends our proof.