Sia n un numero naturale e Q l’insieme dei punti del piano a coordinate intere comprese tra 1 e n (estremi inclusi). Un sottoinsieme di Q é detto nonromboidale se non contiene
4 punti non allineati che formino un parallelogramma. Quanti punti puó contenere al massimo un sottoinsieme nonromboidale di Q?
Scrivo la mia soluzione, sarei grato se mi segnalaste eventuali errori o se mi confermasse la correttezza. Ringrazio in anticipo chi mi risponderà quando avrà un po' di tempo libero.
Soluzione:
Testo nascosto:
Notiamo che i punti di [tex]Q[/tex], formano un quadrato. Notiamo anche che ogni congiungente di due punti di [tex]Q[/tex] può essere visto come la diagonala di un rettangolo con lati paralleli al quadrato iniziale, eventualmente degenere (nei casi di segmenti orizzontali e verticali). Notiamo anche che se due coppie di punti individuano due segmenti congruenti e paralleli allora i quattro punti formano un parallelogramma. Quindi se abbiamo due rettangoli con lati parelleli agli assi x, y e dimensioni [tex]a×b[/tex] con [tex]a,b \leq n-1[/tex] con n definito come nel testo del problema (notimo che non possono avere dimensione n perchè con n punti il lato è al più lungo n-1), due loro diagonali con uguale orientamento determinano un parallelogramma (questo vale anche nel caso degenere di segmenti orizzontali e verticali). Su un quadrato [tex](n-1)×(n-1)[/tex] (con coordinate minori o uguali a n) possiamo costruire tutti i rettangoli le cui dimensioni sono minori o uguali a n-1. Quindi abbiamo un totale di [tex](n-1)(n-1)[/tex] di rettangoli con dimensioni diverse. Ognuno ha due tipi di diagonli, quindi abbiamo [tex]2(n-1)(n-1)[/tex] diagonali che non formano parallelogrammi. Aggiungiamo anche gli 2(n-1) segmenti orizzontali e verticali di lunghezza o verso diverso. Quindi abbiamo un totale di [tex]2(n-1)n[/tex] segmenti che non formono parallelogrammi. Se due si ripetono abbiamo un parallelogramma. Quindi se il sottinsieme individua più di [tex]2(n-1)n[/tex] segmenti si forma un parallelogramma. Il numero di segmenti indivuduato da k punti è [tex]\binom{k}{2}[/tex]. Notiamo [tex]2(n-1)n<\frac{(2n)(2n-1)}{2}=\binom{2n}{2}[/tex] , quindi ci sono al più 2n-1 punti. Notiamo che il sottinsieme formato dalla prima riga e dalla prima colonna ha 2n-1 punti e non ha parallelogrammi. Quindi la risposta è [tex]2n-1[/tex]
Edit: ho fatto delle modifiche alla soluzione, ho corretto alcune cose. Se qualcuno la ha letta prina delle 10:27 8 Agosto, allora non avrà letto la versione corretta (anche se il ragionamento è lo stesso ho corretto alcuni errorri di conteggio)