Il problema del lieto fine

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Il problema del lieto fine

Messaggio da Silver87 »

"Il problema del lieto fine" dai "Cassetti dello Zio Erdos"
(http://utenti.quipo.it/base5/combinatoria/casserdos.htm)
Dati 2^(n-2) +1 punti qualunque su un piano tali che non ve ne siano tre allineati, dimostrare che n di essi formeranno sempre un n-agono convesso.
P. Erdös & G. Szekeres, c. 1932 (?)
Insieme a questo problema sono presentati anche altri 3 con questi titoli:
1-Cinque punti sul piano [...]
2-Nove punti sul piano [...]
3-Diciassette punti sul piano [...]

In realtà tutti questi problemi rientrano in quello chiamato "Il problema del lieto fine" e il suo quesito è questo: 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.

C'è una storia lunga legata a questo problema, ma ora non posso riportarla perché non la ritrovo... mi ricordo solo che il problema "del lieto fine" è così chiamato perché tutte le volte che qualcuno scopriva qualcosa o faceva un passo avanti, poi si sposava... una divertente coincidenza che è ricordata nel titolo!

Espongo il problema sia per chiarirne l'essenza precisa, che per mettere un po' di storia... ed anche perché ci avevo trafficato nel tentativo di risolverlo, nulla di definitivo però ho delle osservazioni che portano sulla buona strada.

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Esempio per il caso del quadrilatero

Messaggio da Silver87 »

Prima delle osservazioni mostro il problema per il primo caso quello del QUADRILATERO è semplice ma aiuta a capire bene la natura del problema:

- premetto che l'esempio che segue non è da considerare una dimostrazione rigorosa, serve solo a comprendere la logica del problema

- ricordo anche che secondo la formula ipotizzata 2^(n-2)+1 risulta per il caso del quadrilatero ovvero n=4, 2^(4-2)+1 = 5 punti per avere sempre almeno 1 quadrilatero convesso.

Nella figura che segue abbiamo tre fasi A, B, C nella fase A ci sono 4 punti è possibile disegnare per quella disposizione un quadrilatero convesso, però nella fase B sempre con 4 punti abbiamo una disposizione in cui non è più possibile avere il quadrilatero convesso, ma al più concavo. Dunque nella fase C aggiungiamo un nuovo punto e con questo nuovo punto sarà inevitabile per qualsiasi posto dove viene messo, avere almeno un quadrilatero convesso (in figura C è colorato in grigio). Quindi possiamo dire graficamente che 5 punti sono sufficienti ad avere sempre un quadrilatero convesso per qualsiasi loro disposizione. Il risultato è concorde con la formula ipotizzata.
Allegati
Figura A, B e C del caso del quadrilatero
Figura A, B e C del caso del quadrilatero
QuadrilateroABC.GIF (923 Byte) Visto 79401 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Caso del pentagono

Messaggio da Silver87 »

E' stato dimostrato da un certo personaggio di cui non ricordo il nome che il problema del lieto fine per il caso del pentagono viene risolto dalla figura in allegato, infatti se aggiungiamo un punto alla disposizione in figura (composta di 8 punti) sarà inevitabile avere almeno un pentagono convesso.

Il risultato è concorde con la formula ipotizzata: 2^(5-2)+1 = 9 punti (infatti 8 sono nella figura poi con l'aggiunta di 1 altro, fanno 9 punti)
Allegati
Disposizione di 8 punti che non consentono di disegnare un pentagono convesso
Disposizione di 8 punti che non consentono di disegnare un pentagono convesso
Pentagono.GIF (1.16 KiB) Visto 79400 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

OSSERVAZIONI

Messaggio da Silver87 »

Queste sono delle osservazioni generali e particolari legate a questo problema:

1°) Riguardo la formula 2^(n-2)+1, non è sicuro che sia vera anche se sembra di sì, se fosse corretta possiamo notare che la parte significativa della formula è 2^(n-2) questa operazione restituisce il numero di punti massimo per cui esiste una particolare disposizione che non consente di disegnare nessun poligono di n lati convesso. E' praticamente un altro modo di vedere il problema, infatti credo sia logicamente più facile trovare questa disposizione che non consente poligoni convessi e infine considerare un punto in più (come una goccia che fa traboccare il vaso) piuttosto che trovare i punti che danno soluzione al problema e valgono per qualsiasi disposizione di tali punti rendendo le cose "troppo flessibili".

2°) Quindi (è solo un ipotesi) si potrebbe andare in cerca di una dimostrazione che esiste una disposizione (come quella definita prima) che possiamo chiamare "PEGGIORE" e "ULTIMA", "peggiore" perché è il caso particolare che NON consente di avere neanche un poligono convesso, "ultima" perché se aggiungiamo solo 1 altro punto sarà impossibile non avere un poligono convesso.

3°) Sempre considerando valida la formula 2^(n-2)+1, e vediamo la tabella dei risultati:

n° lati poligono | n° punti 2^(n-2)+1
______4______|_______5________
______5______|_______9________
______6______|______17________
______7______|______33________
______8______|______65________
______9______|_____129________
_____10______|_____257________

se notiamo le soluzioni, cioé il numero di punti, vediamo che la soluzione successica è uguale alla precedente meno 1 punto, matematicamente è facile dimostrare che è sempre così:

2^(n-2)+1 = (2^(n-1-2)+1)*2-1 (questa è la tesi, sposto 1 al 1° membro)
2^(n-2)+2 = (2^(n-1-2)+1)*2 (divido tutto per 2)
2^(n-2-1)+1 = 2^(n-1-2)+1
2^(n-3)+1 = 2^(n-3)+1 (la tesi è infatti una identità)

Matematicamente serve a poco o niente, ma graficamente si potrebbe dire: i punti del caso precedente vengono raddoppiati eccetto un punto, che rimane anche se non raddoppiato. E' solo un'idea magari sviluppata ne esce qualcosa in più...

4°) Consideriamo cosa vuol dire analiticamente convesso e concavo:
- se dovessimo far verificare a un computer se dati n punti questi fanno un poligono convesso o no, la cosa è un po' scomoda da gestire, dovremmo infatti costruire tutte le rette prendendo i punti 2 a 2, poi ciascuna retta occorre verificare se presenta i rimanenti punti solo da una delle sue due parti in cui divide il piano, se ci sono punti da entrabe le parti è sicuramente concavo.

- un altro metodo analiticamente più veloce è questo: consideriamo che preso un poligono di n lati sarà sufficiente prendere tutti i possibili gruppi di 4 punti che si formano, per ciascun gruppo valutare se è convesso o concavo, infatti se 4 punti fanno un quadrilatero concavo aggiungendo punti (quindi con poligoni di più lati) sarà impossibile realizzare un poligono convesso! Quindi il caso ricade in tanti quadrilateri invece di un poligono di n lati, il quadrilatero per sapere se è convesso o concavo basta calcolare l'area dei 4 triangoli possibili che si formano, prendere quello con l'area maggiore e verificare: se la somma dei 3 più piccoli è uguale a quello grande abbiamo un quadrilatero concavo, se è maggiore la somma dei 3 rispetto a quello più grande è convesso.

Mi rendo conto che a parole sembra più complicato il secondo metodo, ma nel primo ho tralasciato alcuni sotto-problemi terribili da far risolvere a un computer, mentre il 2° è estremamente più facile, posso assicurarlo perché un simile programma lo realizzato in Visual Basic e il 2° metodo è un "razzo" rispetto al 1°.

5°) Ultima osservazione generale se è vera la formula 2^(n-2)+1 significa che la soluzione del problema non dovrebbe coinvolgere chissà quali metodi e procedure analitiche (come finora ho fatto principalmente...) ma dovrebbe esser sufficiente trovare qualche proprietà che ha a che fare con la quantità e non il tipo di disposizione dei punti! Però nulla è sicuro, sono tutte ipotesi...

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Il caso dell'esagono

Messaggio da Silver87 »

In merito al problema del lieto fine ho sviluppato un programma in Visual Basic per cercare la "disposizione peggiore ultima" (per definizione vedi sopra) del caso del quadrilatero, pentagono, esagono. Di seguito ci sono delle immagini in cui non è possibile costruire il relativo poligono convesso, e con un solo punto in più diventa sempre possibile. Le immagine non sono né una dimostrazione, né un dato sicuro, però qualcosina sono... Inoltre i risultati concordano tutti con la formula 2^(n-2)+1

Devo aggiugnere un ultima cosa: le disposizioni "peggiori ultime" non sono uniche hanno lo stesso numero di punti, e questo è fondamentale, ma è da notare che non sono disposizioni uniche!! Io non metto le varianti... scelgo solo quelle significative.

N.B.
I tempi del programma per trovare la soluzione sono relativamente lunghi, e occorre una super-visione (non per evitare errori ma per mandare avanti la ricerca...) ci sono alcuni piccoli problemi tecnici, infatti il caso dell'ettagono non sono riuscito ad ottenerlo ancora con una solida sicurezza. Le immagini mostrate sono attendibili al 100%, questo non significa che non esistono disposizioni con più punti che non consentono di disegnare un poligono di n lati convesso, ma certamente non troverete tra le disposizioni di questi punti la possibilità di disegnare un poligono convesso.
Allegati
Caso dell'esagono: trovati 16 punti
Caso dell'esagono: trovati 16 punti
CPU Esagono.GIF (46.94 KiB) Visto 78221 volte
Caso del pentagono: trovati 8 punti
Caso del pentagono: trovati 8 punti
CPU Pentagono.GIF (8.63 KiB) Visto 79382 volte
Caso del quadrilatero: trovati 4 punti
Caso del quadrilatero: trovati 4 punti
CPU Quadrilatero.GIF (3.23 KiB) Visto 79383 volte

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Messaggio da giobimbo »

Prima di tutto dico "bravo" a Silver87, per aver affrontato un problema tutt'altro che semplice, per la soluzione con 16 punti, per le sue considerazioni che mi trovano abbastanza d'accordo.

Per quelli incuriositi dal problema, poi, aggiungo alcune notizie. Negli anni '30 del secolo scorso, un gruppo (variabile) di studenti dell'università di Budapest si ritrovava fuori dalla scuola per fare discussioni e passeggiate; Esther Klein a volte ne faceva parte e fu lei a tirar fuori e dimostrare il problema del quadrilatero con 5 punti. Paul Erdos lo allargò al caso generale e con Szekeres dimostrò che il numero di punti g(n) per cui esiste un poligono di n lati dev'essere:
$2^{n-2}+1 \leq g(n) \leq {{2n-4} \choose {n-2}}+1$ (E.Weisstein - Mathwordl)
$2^{n-2}+1 \leq g(n) \leq {{2n-4} \choose {n-2}}$ (AA.VV - Handbook of Combinatorics)
$2^{n-2} \leq g(n) \leq {{2n-4} \choose {n-2}}+1$ (D.B.West - Introduction to Graph Theory)
(??? forse la formula giusta è la seconda, visto che Erdos ha scritto quella voce del manuale, ma non è detto...)
Alcuni anni più tardi la Klein e Szekeres si sposarono - da qui il nome dato da Erdos di happy ending problem - e vissero felici e contenti fino all'anno scorso, quando morirono ambedue nel giro un'ora.
Se si cerca "happy end problem" nel sito http://www.mathworld.com si vede che è nota l'esistenza di una disposizione di 16 punti che non contiene un esagono.

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Varianti dei casi precedenti

Messaggio da Silver87 »

Ringrazio giobimbo per aver apprezato il lavoro! :D

Volevo mettere delle varianti significative per il caso del pentagono e dell'esagono, il numero dei punti resta invariato e sempre concorde con la formula 2^(n-2)+1, ma cambia la disposizione in modo fondamentale, non so quante varianti esistono... comunque eccole qua sotto:
Allegati
CPU Esagono 2.GIF
Caso dell'esagono: 16 punti
(58.04 KiB) Scaricato 1666 volte
Caso del pentagono: 8 punti
Caso del pentagono: 8 punti
CPU Pentagono 2.GIF (7.74 KiB) Visto 79350 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Novità sul problema del lieto fine

Messaggio da Silver87 »

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! :D
Allegati
convessita-concavita.gif
convessita-concavita.gif (2.3 KiB) Visto 78947 volte
poligoni-da-scartare.gif
poligoni-da-scartare.gif (2.75 KiB) Visto 78952 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Osservazioni - 2° parte

Messaggio da Silver87 »

Aggiungo altre interessanti osservazioni per ragionare sul problema:

- il triangolo è il poligono con il minor numero di lati che si possa disegnare sul piano cartesiano, è la porzione "minima di piano" che si possa definire, non minima nel senso di piccola (poco estesa) ma "minima" perché la prima che può definire una parte di piano limitata (3 lati - 3 punti).

- ne segue che il quadrilatero è il primo che può essere convesso o concavo, perché definita la porzione "minima" (triangolo) se "aggiungiamo" un altro triangolo abbiamo un quadrilatero convesso, se "leviamo" una porzione "minima" alla porzione già presente, abbiamo una concavità (quadrilatero concavo), vedi allegato "triangoli".

- dato un certo numero di punti p per sapere quanti triangoli possiamo disegnare con questi punti, praticamente quanti insiemi di 3 punti si possono formare dato un numero di punti p > 2, la formula è n. triangoli t = (p^3 / 6) - (p^2 / 2) + (p / 3)

- non sono riuscito a mettere in relazione le precedenti osservazioni, ma si potrebbe provare a considerare quando un certo numero di triangoli che si formano per un certo numero di punti obbliga almeno 2 triangoli a disporsi in modo non sovrapposto e quindi a dare un quadrilatero convesso.

- per ultimo insisto tanto sul caso del quadrilatero perché trovo che sia un caso "chiave" del problema, infatti per i successivi poligoni si tratta di quadrilateri convessi che si "legano" insieme, per capire bene (e questo trovo sia importante) vedi l'allegato "poligoni".
Allegati
poligoni.GIF
poligoni.GIF (7.81 KiB) Visto 78921 volte
triangoli.GIF
triangoli.GIF (3.32 KiB) Visto 78917 volte

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Messaggio da giobimbo »

Penso anch'io che sia importante considerare i quadrilateri, i triangoli sono tutti uguali quindi non ci danno tante informazioni, invece i quadrilateri sono di due tipi, concavi o convessi; inoltre se m degli n punti formano un m-gono convesso allora questi m punti formano anche ${m \choose 4}$ quadrilateri convessi.
Usare il computer per provare tutte le possibili disposizioni di n punti ci può dare dei suggerimenti per piccoli valori di n, ma dopo poco diventa impossibile procedere, occorre basarsi sulla topologia dei punti oppure sulla loro combinatoria (il principio dei cassetti, appunto).

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

2° metodo per costruire poligoni convessi

Messaggio da Silver87 »

Volevo aggiungere ancora un'idea, in un allegato precedente (quello subito sopra) che si chiama "poligoni.gif" ho mostrato come costruire poligoni di m lati basandosi sul quadrilatero, sempre con il quadrilatero è possibile procedere in un altro modo, forse un po' più insolito, ma di primo impatto (forse mi sbaglio) sembra essere più "generalizzabile".

Il 2° metodo consiste nel partire da un quadrilatero, cioè da 2 segmenti intersecati, quelli che nelle tre figure qui sotto (allegato: "metodo2.jpg") sono viola, poi per ottenere di volta in volta un poligono con un lato in più rispetto al precedente, si deve tracciare un segmento su un lato del quadrilatero viola, e a partire dai 2 estremi rimasti liberi del quadrilatero viola, si fanno uscire altri 2 segmenti che intersecano il lato e avranno l'estremo finale in comune, questi 3 segmenti sono quelli nella seconda figura di colore verde, stesso identico procedimento per l'esagono, i 3 segmenti sono arancio.

La cosa saliente è che la costruzione è identica per passare da un poligono a quello superiore (la costruzione in verde e quella in arancio sono uguali), ecco perché mi sembra più facile da generalizzare, inoltre nel 1° metodo si prevede un "riallacciamento" dei quadrilateri per chiudere il "giro" e formare il nuovo poligono, qui non c'è questo "riallacciamento" che matematicamente non saprei come definire o considerare.

Ho anche dimostrato parzialmente (diciamo che non mi soddisfa ancora) quanti punti servono per avere sempre questa particolare struttura (verde e arancio in allegato, che è 2 segmenti con 1 estremo in comune tagliati entrambi da un altro segmento), ma poi manca ancora qualche passo per risolvere il problema del lieto fine (e non credo siano passi facili, anche se pochi).
Allegati
metodo2.JPG
metodo2.JPG (19.48 KiB) Visto 78891 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Tentativo di dimostrazione

Messaggio da Silver87 »

Qual è il numero minimo di punti, tali per cui per qualsiasi loro disposizione sul piano cartesiano, è sempre possibile disegnare 2 segmenti con 1 estremo in comune tagliati entrambe da 1 altro segmento?

Questo è il problema che emerge dalla "struttura" evidenziata nel post precedete, quella che nel precedente allegato era verde o arancio, certo questo sotto-problema del prob. del lieto fine, una volta risolto non risolve niente, per il momento, ma forse continuando su questa strada potrà rivelarsi utile, non lo so... :?:

Partiamo con un presupposto: 2 quadrilateri con 3 punti in comune garantiscono sempre una soluzione al sotto-problema, dimostrazione (seguire i passi guardando l'allegato '2quadrilateri.jpg'): un quadrilatero sono 2 segmenti intersecati chiamiamoli coppia di segmenti neri (N), per condividere 3 estremi con un altra coppia di segmenti intersecati, che chiameremo coppia blu (B), avverrà necessariamente che un segmento della coppia B congiunga 2 estremi della coppia N, l'altro segmento della coppia B deve partire da un estremo della coppia N perché gli estremi da condividere sono 3 (e ancora eravamo a 2), poi dato che i 2 segmenti della coppia blu, a causa del presupposto danno un quadrilatero, significa che si intersecheranno, ed ecco che a questo punto abbiamo tracciato quel che si vede nell'allegato '2quadrilateri.jpg'

Osserviamo come siano inevitabili nella figura ben 2 casi contemporanei, direi "congiunti" o "consecutivi", di 2 segmenti con 1 estremo in comune tagliati entrambe da un altro segmento, quasi sembra un pentagono ma non lo è, basta prolungare abbastanza (e magari inclinare in modo appropiato) uno dei 2 segmenti dalla parte in cui hanno l'estremo libero (vedi figura) affinché il pentagono non si possa disegnare. Fatto questo chiarimento, possiamo riformulare il sotto-problema iniziale dicendo: Qual è il numero minimo di punti, tali per cui per qualsiasi loro disposizione sul piano cartesiano, è sempre possibile disegnare 2 quadrilateri con 3 estremi in comune?

Ebbene a seguito di questo problema riformulato invito a guardare l'allegato 'Q6punti.jpg' non è una vera dimostrazione, ma diciamo un indizio forte e convincente, possiamo vedere ben 3 coppie di segmenti intersecati (quadrilateri) che condividono 2 estremi ciascuno con gli altri 2 "compagni" quadrilateri, diciamo che è un caso limite, è il massimo di presenza di quadrilateri e di condivisione di punti possibile che ancora non soddisfa il requisito del sotto-problema, è chiaro suppongo che l'aggiunta di un punto fa "crollare" l'equilibrio e ci sarà almeno una coppia di quadrilateri che condividerà 3 punti tra loro.

Quindi suppongo che 7 punti necessariamente consentono di disegnare 2 quadrilateri con 3 estremi in comune, cioè almeno un caso in cui ci sono 2 segmenti con 1 estremo in comune tagliati entrambe da 1 altro segmento, tale caso è quello (stando al post precedente) che deve ripetersi costruendosi "sopra" il precedente poligono per generare il poligono convesso successivo. (questa conclusione sembra una strada abbozzata verso la meta che è la soluzione del prob. del lieto fine, non trovate? io non lo so, ho provato altre strade che sono totalmente crollate, però questa volta ho una speranza migliore... :) )

Non ho dimostrato nulla, nè fornito soluzioni, lo so :( però mi sembrano idee interessanti spero ne venga fuori qualcosa, magari suggeriscono nuovi approcci...
Allegati
Q6punti.JPG
Q6punti.JPG (11.92 KiB) Visto 78876 volte
2quadrilateri.JPG
2quadrilateri.JPG (6.02 KiB) Visto 78878 volte

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Disposizioni di punti problematiche

Messaggio da Silver87 »

E' passato del tempo, ogni tanto mi occupo del problema del lieto fine, ho perfezionato alcuni programmi che avevo fatto per trovare la disposizione di punti peggiore e ultima (vedi post precedenti) per ogni poligono. Ero arrivato all'esagono e ancora non ho trovato quella per l'ettagono, ho finalmente capito perché non la trovavo.

Io avevo ipotizzato (ne ero molto sicuro a dire il vero...) che data una disposizione di punti sul piano era sempre possibile aggiungere un punto finché non si raggiungeva il limite critico. Invece ho scoperto che ci sono alcune disposizioni per l'esagono che hanno 15 punti e non c'è modo di aggiungerne un altro senza fare un esagono convesso, eppure se quei punti vengono disposti diversamente allora si riesce ad inserire ancora un punto e si arriva a 16, il limite oltre il quale non si può andare.

In allegato ci sono ben 2 casi per l'esagono in cui ci sono 15 punti disposti sul piano e le relative coordinate (a chi interessano) e tenendoli fissi non c'è modo di aggiungere un nuovo punto. La seconda disposizione è precisa ed elegante, la prima è più confusionaria, anche se comunque corretta.

Quando ricercavo l'ettagono a volte mi fermavo a 28 punti, 29, 27... il massimo che sono riuscito ad ottenere è stato 30 punti, pensavo che questa variazione dipendesse dal numero davvero tremendo di rette e zone che si generano che non erano sistematicamente consultate, credevo mi sfuggisse qualcosa... (è in parte automatico e in parte manuale il programmino che ho fatto...), invece migliorando molte cose ho capito che i punti non possono essere disposti a caso e interrogate tutte le zone, ma devono essere disposti con una logica, quella che consente l'inserimento del maggior numero di punti possibile. Quale sia questa logica non lo so... ed io agendo a caso non ho mai beccato la disposizione dei 32 punti. Però ora che so che le cose stanno così anche se la trovo da 32 chi mi dice che non ce ne sia una da 33 o 34, e quindi questo genere di ricerca è inutile... :(

Concludo che il tutto conferma che la ricerca deve essere puramente teorica e astratta, non affidata a ricerche di questo genere... ed io che speravo a breve di vedere le disposizioni di molti poligoni (fino al decagono o quasi)

Saluti a tutti! E buon Capodanno!! :)
Allegati
CasoEsagono-15p_2.gif
(1.92 KiB) Scaricato 628 volte
CasoEsagono-15p_1.gif
CasoEsagono-15p_1.gif (15.61 KiB) Visto 77153 volte

fabiuz
Nuovo utente
Nuovo utente
Messaggi: 10
Iscritto il: mer mar 26, 2008 9:38 am

Re: Il problema del lieto fine

Messaggio da fabiuz »

Scusate, ci sono un paio di punti che non capisco di questo problema e forse mi potete dare una delucidazione in proposito, essendo io appassionato di matematica ma non matematico.


domanda 1:
detto g(n) il numero minimo di punti per cui vale la proprietà da dimostrare, si potrebbe procedere dimostrando "facilmente" :roll: 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 :) ). E del resto pare di capire che questa metà del problema sia già stata risolta da Erdos e colleghi.
Quello che mi è completamente oscuro è come procedere per dimostrare che NON esiste alcun controesempio per un dato numero di punti maggiore di 2^(n-2)+1. Prendiamo il caso con 6 punti, tanto per chiarire. La formula mi dice che 17 punti dovrebbero bastare a trovare un esagono. Ma come faccio a dimostrare per via NON geometrica che con 100 punti c'è SEMPRE almeno un esagono? Voi come fareste?
E' chiaro che la mia idea sarebbe di partire da un limite superiore abbastanza alto (anche molto maggiore di quelli dimostrati sinora) e poi avvicinarsi gradatamente, raffinando via via quel limite (che mi pare sia un po' quello che è stato fatto finora). Solamente che i matematici di professione lo hanno fatto per via astratta (probabilmente il metodo in assoluto migliore) e vorrei capire almeno da dove partire. Chi mi dà gentilmente una dritta?

domanda 2, di argomento più generale

dati gli n punti e g(n)= 2^(n-2) +1 del quesito irrisolto: il quesito si può risolvere SOLAMENTE dimostrando un limite superiore e un limite inferiore a g(n) e trovando che sono pari a 2^n-2 e 2^(n-2) +2 oppure, matematicamente parlando, ci sono anche altre strade standard per questa "classe" di problemi? e se sì quali?

Silver87
Nuovo utente
Nuovo utente
Messaggi: 16
Iscritto il: lun ago 14, 2006 1:12 pm

Risposta alle domande di fabiuz

Messaggio da Silver87 »

fabiuz ha scritto:Prendiamo il caso con 6 punti, tanto per chiarire. La formula mi dice che 17 punti dovrebbero bastare a trovare un esagono. Ma come faccio a dimostrare per via NON geometrica che con 100 punti c'è SEMPRE almeno un esagono? Voi come fareste?
E' molto semplice con la logica, è un fatto necessario. Se 17 punti sono sufficienti per disegnare almeno 1 esagono convesso per qualsiasi loro disposizione, e tu di punti me ne dai 100, io 83 li ignoro, considero un sottoinsieme di 17 punti nei 100 punti, e certamente potrò disegnare il mio esagono convesso. Sono cose così ovvie che a volte sfuggono, oppure ti ho capito male...
fabiuz ha scritto:E' chiaro che la mia idea sarebbe di partire da un limite superiore abbastanza alto (anche molto maggiore di quelli dimostrati sinora) e poi avvicinarsi gradatamente, raffinando via via quel limite (che mi pare sia un po' quello che è stato fatto finora). Solamente che i matematici di professione lo hanno fatto per via astratta (probabilmente il metodo in assoluto migliore) e vorrei capire almeno da dove partire.
Dato che una dimostrazione, o meglio una reale comprensione del "meccanismo" di questo problema non si è raggiunta, si è tentato (in buona parte riuscendoci) di inquadrare il numero di punti della soluzione per un poligono di n lati, tra un minimo e un massimo. Io purtroppo non ho la competenza matematica per capire come fanno a stabilire minimi e massimi, e quindi non posso aiutarti nella comprensione. Il mio è un approccio geometrico, diciamo da "profano", siccome certi problemi mi divertono, cerco di risolverli con la logica e considerazioni elementari di geometria.
fabiuz ha scritto:dati gli n punti e g(n)= 2^(n-2) +1 del quesito irrisolto: il quesito si può risolvere SOLAMENTE dimostrando un limite superiore e un limite inferiore a g(n) e trovando che sono pari a 2^n-2 e 2^(n-2) +2 oppure, matematicamente parlando, ci sono anche altre strade standard per questa "classe" di problemi? e se sì quali?
I tentativi che sono stati fatti sono una strada percorribile, ma "a priori" non possiamo sapere se ce ne sono altre e quali sono, occorre provare e cercarle, io in gran parte mi baso sulla geometria, anche perché il problema è essenzialmente geometrico, almeno mi pare. Prova a leggere il problema, considera quello che fai per cercare le soluzioni, anche in casi specifici e semplici (la generalizzazione viene dopo), e cerca di capire il "meccanismo" del problema: perché aggiungendo progressivamente punti sul piano cartesiano dopo un "limite critico" diventa possibile disegnare un poligono convesso per qualsiasi loro disposizione, oppure cosa significa che la posizione dei punti non conta ma solo il loro numero, può suggerire questa considerazione di abbandonare un approccio geometrico per uno più astratto? Per me, devo dire che è stato così.

Purtroppo non posso esserti molto utile, a causa delle mie troppo semplici conoscenze matematiche. E' un po' di tempo che non mi occupo di questo problema per via di vari impegni... ma in base ai periodi mi ci applico.

Rispondi