JBTST IV 2008, Problema 2

[Laurian Filip]

Fie m, n doua numere naturale nenule si multimile \( A=\lbrace 1,2,3,...,n} \), \( B=\lbrace 1,2,3,...,m} \). Spunem ca o submultime \( S \) a produsului cartezian \( AxB \) are proprietatea (j) daca \( (a-x)(b-y)\leq 0 \), pentru orice perechi \( (a,b),(x,y)\in S \). Sa se arate ca orice multime S cu proprietatea (j) are cel mult \( m+n-1 \) elemente.

[mihai++]

Consideram tabelul \( \left(A_{ij}\right) \), \( 1\leq i\leq n \), \( 1\leq j\leq m \).
Fie \( \left(a_0,b_0\right) \) cel mai apropiat punct de \( \left(1,1\right) \). Concluzia se traduce prin faptul ca pornind cu linia franta ce uneste elementele multimii \( S \) putem sa mergem ori la dreapta ori in jos. Cea mai lunga linie franta cu aceasta proprietate are lungimea \( m+n-1 \). O astfel de linie franta este \( \left(1,1\right)-\left(1,m\right)-\left(m,n\right) \).
Analog se gandeste luand punctul cel mai apropiat de orice colt al tabelului.

Am considerat tabelul aratand astfel:
1 2 3 4 5 ... m
1
2
3
4
.
.
.
n