Puncte laticeale - JBTST VI 2007, problema 2

[Filip Chindea]

Fie intregii \( 1 \le m < n \). Consideram multimea \( M = \{ (x,y) :\ x, y \in \mathbb{N},\ 1 \le x, y \le n \} \). Determinati valoarea minima \( v(m,n) \) cu proprietatea ca oricare ar fi \( P \subseteq M \) cu \( |P| = v(m,n) \) exista \( m+1 \) elemente \( A_i = (x_i,y_i) \in P \) cu \( i = 1, 2, ..., m + 1 \), cu toate \( x_i \) distincte si \( y_i \) de asemenea distincte.

[Marius Mainea]

\( v(m,n)=m\cdot n+1 \)

In curand si demonstratia.

[Laurian Filip]

Am stiut aproape toti ca asta e valoarea minima, dar nu am stiut sa demonstram ca este suficienta...

[Beniamin Bogosel]

Demonstram afurmatia pentru un \( n \) dat prin inductie dupa \( m \).

Pentru \( m=1 \) este evident. Exista doua puncte din cele \( n+1 \) puncte care au ambele coordonate distincte pentru ca altfel ar trebui ca toate punctele sa se afle pe o dreapta, ceea ce e imposibil, pentru ca pe o dreapta din multimea respectiva exista maxim \( n \) puncte.

Presupunem acum ca pentru \( mn+1 \) puncte gasim \( m+1 \) puncte ca si in enunt. Presupunem deasemenea ca \( m<n-1 \) ca sa putem vorbi de \( m+1 \). Avem \( n(m+1)+1=mn+1+n \) puncte. Printre primele \( mn+1 \) gasim folosind ipoteza de inductie \( m+1 \) puncte cu ambele coordonate distincte. Presupunem acum ca oricare alt punct din multimea \( P \) care are coordonata \( x \) diferita de a celor \( m+1 \) gasite anterior, are coordonata \( y \) egala cu a unuia dintre cele \( m+1 \) puncte consideate. Atunci toate punctele ar trebui sa se afle pe \( m+1 \) paralele la dreapta \( Ox \). Prin urmare ar fi cel mult \( n(m+1)=mn+n \) puncte. Dar noi avem cu exact unul mai multe. Prin urmare exista un alt punct diferit de cele \( m+1 \) care are ambele coordonate diferite de coordonatele altui punct dintre cele \( m+1 \). Astfel putem gasi \( m+2 \) puncte cu proprietatea ceruta.

Astfel am demonstrat prin inductie ca pentru orice \( m,n \) naturale cu proprietatile din enunt proprietatea are loc.