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.
