E' molto tempo che ho "lasciato" il problema del lieto fine, però ogni tanto l'ho ripensato e senza elencare i vari insuccessi e "strade" abbandonate, sono giunto ad alcune osservazioni che trovo molto interessanti e credo di intravedere la pista giusta per arrivare alla soluzione del problema (almeno spero...
) premetto infine che nelle osservazioni che seguono ripeterò qualcosina che già avevo detto nei post passati, ma per ragioni di completezza ho bisogno di ripetermi leggermente.
Partiamo dal quesito del problema:
trovare il numero di punti tali che non ve ne siano 3 allineati e sia possibile disegnare almeno un poligono di n lati convesso per qualsiasi disposizione di tali punti sul piano cartesiano.
Osservazioni:
1°) Nelle pagine precedenti ho mostrato delle disposizioni di punti e questo è utile per ragionare ed avere indizi, però dato che il problema si basa su un
numero di punti da trovare, e dice anche
per qualsiasi disposizione, significa in altre parole A PRESCINDERE DALLA DISPOSIZIONE, sembra una sottigliezza ma questo sprona secondo me a cercare più un principio generale o una o più regole, piuttosto che disegnare casi e disposizioni per arrivare alla soluzione.
2°) Che un poligono sia concavo o convesso, non serve immaginarlo come una retta spezzata chiusa, perché ho visto che nei ragionamenti (almeno quelli che ho fatto io...) complica assai le cose, mentre in realtà è molto più facile e corretto considerare che la CONCAVITA' si ha quando c'è un insieme di 3 punti che "contiene" un qualsiasi altro punto di quelli che sarebbero i vertici del poligono se si tracciano i lati (magari queste sono cose note a tutti, ma io non sapendo molte cose, dato che mi sembrano osservazioni interessanti per premura le espongo, poi forse sembreranno banalità...)
2°b) Segue dal punto 2° che la "chiave di volta" del problema è il caso del quadrilatero perché è lui il primo ed il solo a determinare la concavità in un qualsiasi poligono, immaginiamo un poligono come un insieme di punti, se ci sono 3 punti che contengono un quarto punto certamente tutto il poligono è concavo.
3°) (
ora inizia la parte interessante) se non pensiamo più a disegnare lati per trovare un poligono, non c'è più bisogno nella ricerca (manuale o teorica) dei poligoni in una disposizione di punti, di "scartare" quelli che si intrecciano, cioè di trovare "significativi" degli insiemi di collegamenti da punto a punto e "non significativi" altri insiemi di collegamenti da punto a punto (per collegamenti intendo lati ma in modo da considerarli sotto un altro profilo), l'immagine "poligoni da scartare" in allegato chiarisce meglio cosa intendo.
3°b) ora espongo l'idea per rendere sensato ogni tipo di collegamento in una disposizione così da permettermi un approccio teorico senza lavorare sulla disposizione, ma con regole generali, invece di vedere i lati del
quadrilatero (questa è la "figura perno" della questione) ho considerato come è la sua "struttura" quando è convesso e quando non lo è, ebbene se si guarda l'allegato "convessità-concavità" si capisce bene. Tutte le volte che i punti nella disposizione consentono di disegnare 2 segmenti intersecati abbiamo sicuramente un quadrilatero convesso, se non ci sono segmenti che si intersecano avremo al più quadrilateri concavi.
4°) gettando un rapido sguardo su una possibile generalizzazione (che poi riprenderò meglio in un prossimo post) del principio alla base della convessità o concavità, cioé la ricerca di segmenti intersecati, capiamo bene che per un pentagono le cose si complicano ma il principio è sempre quello, vi è una certa "configurazione" di segmenti intersecati che danno origine, per il pentagono, alla stella a 5 punte che si disegna senza mai staccare la penna, il pentagramma, ebbene in qualunque modo lo disegnate (più "stiracchiato", con una punta molto grande, etc.) potete sempre disegnare un pentagono, ma il pentagramma è appunto una costruzioni di "quadrilateri convessi" o meglio di segmenti intersecati e così si va avanti (ma le cose non sono facili, né risolte ancora...)
Fine delle osservazioni, passo invece a dimostrare il caso del quadrilatero, è stato già fatto ed è banale farlo, ma non è il risultato che mi interessa quanto un nuovo modo di dimostrarlo: (
i passaggi che seguono sono un po' intricati li ho messi perché volevo creare una dimostrazione completa ed ho prevenuto alcune critiche che mi ero auto-fatto con ulteriori passaggi, ma il vero succo del discorso e racchiuso nel punto 6)
1) Un quadrilatero è convesso quando è possibile disegnare 2 segmenti intersecati, quindi possiamo considerare un quadrilatero come 2 segmenti intersecati.
2) Un quadrilatero può essere anche concavo quindi 4 punti non sono sufficienti per soddisfare il problema, e certamente servono almeno 4 punti per disegnarne uno concavo o convesso che sia, e dunque partiamo da 4 punti sul piano, senza considerare la loro precisa disposizione, dato che ci interessa solo il numero di punti ed eventuali proprietà.
3) Consideriamo ora che siamo su un piano bidimensionale, in cui il poligono con il minor numero di lati possibile da disegnare è il triangolo, se vi fosse una disposizione di punti tale per cui un numero x di punti, tracciati tutti i possibili segmenti non presentasse nessuna coppia di segmenti intersecati, avremmo certamente uno spazio tutto diviso in triangoli.
4) Quindi possiamo essere certi che dei 4 punti da cui partiamo 3 formeranno un triangolo, ed il 4° sarà necessariamente dentro il triangolo, altrimenti avremmo subito un quadrilatero convesso, che non deve venire per nostra scelta ma per necessità dal numero dei punti che si prende, inoltre dovendo disegnare tutti i segmenti con questi punti, è logico che dal 4° punto usciranno 3 segmenti diretti verso gli altri 3 punti del triangolo iniziale. Dato che il 4° punto è dentro quel triangolo, i 3 segmenti finiranno sui 3 vertici del triangolo e non avremo nessuna intersezione, quindi 4 punti non soddisfano il problema.
5) Aggiungiamo un 5° punto, lo spazio è sicuramente diviso in triangoli per il motivo spiegato nel 3° passo, il 5° punto sarà dunque dentro un triangolo, se il 5° punto fosse messo fuori da un triangolo avremmo o un quadrilatero convesso, ma tale quadrilatero non deve venire a seguito di una scelta ma a seguito della necessità suddetta, oppure può accadere che il 5° punto con i due punti del lato di un triangolo esistente, mandi dentro il nuovo triangolo che viene a formarsi il rimanente vertice del triangolo esistente, però così facendo vi è solo un passaggio di "ruolo": la condizione che avrebbe incontrato il 5° punto, non la incontra più, ma fa sì che un punto esistente viene messo nella stessa condizione che il 5° punto avrebbe incontrato, e quindi che sia un punto od un altro a creare tale condizione è indifferente, ciò che conta è la condizione stessa.
6) Dunque la condizione del 5° punto è che si trova dentro un triangolo ed escono da esso 4 nuovi segmenti, adesso avendo il triangolo solo 3 vertici, 3 segmenti finiranno sui 3 vertici del triangolo ed il 4° segmento dovrà necessariamente tagliare un lato del triangolo, quindi avremo una coppia di segmenti intersecati. Concludendo 5 punti a prescindere dalla loro disposizione necessariamente determinano l'intersezione di 2 segmenti, cioè la possibilità di disegnare un quadrilatero convesso.
Fine dimostrazione (non so se è proprio accettabile una cosa così... spero di aver fatto comprendere l'idea di base)
Una cosa più semplice (ma comprensibile dopo aver letto i passi precedenti) è considerare che da un punto, in una disposizione, partono tanti segmenti (s) quanto il totale dei punti (p) della disposizione meno 1, quindi s = p - 1.
Adesso non avendo ancora nessun intersecamento di segmenti, abbiamo il piano diviso in triangoli (poligono con il minor numero di lati), se un punto è interno al triangolo possono uscire al massimo 3 segmenti dal punto che finiscono sui vertici senza intersecamenti, ma se abbiamo 4 segmenti che escono dal punto, i 3 vertici del triangolo non bastano più e il 4° segmento taglierà un lato del triangolo e l'intersecamento sarà inevitabile, quindi s = 4 (limite critico) secondo la precedente s = p - 1 segue 4 = p - 1, cioè p = 5 soluzione del caso del quadrilatero, semplice no? (peccato che per il pentagono poi ho perso la testa...)
Ho altro da dire ma per il momento basta così... aspetto volentieri qualche parere sperando che la questione sia interessante. Ciao!
però mi sembrano idee interessanti spero ne venga fuori qualcosa, magari suggeriscono nuovi approcci...
un limite inferiore a g(n), ad esempio trovando un controesempio con 2^(n-2) punti (magari c'è un diagramma abbastanza generale, in cui raddoppiando i punti di volta in volta non si creano n-agoni convessi). Oppure per via astratta, sempre un limite inferiore; ma in definitiva così si è risolto solo metà del problema, la parte per così dire "facile" (non che saprei farlo, per intenderci