Il problema del lieto fine

[fabiuz]

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...

No, scusa, temo che non mi sono spiegato bene. E' OVVIO che se la proposizione è dimostrata allora con 100 punti c'è sempre almeno un esagono....ma non è dimostrata !!!
Quindi come faccio a dimostrare per via NON geometrica che con 100 punti c'è SEMPRE almeno un esagono? Come si fa a dimostrare che NON esiste un controesempio con un dato insieme di punti?

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,

Certo che possiamo sapere se ce ne sono altre! Qui la domanda però è rivolta a un matematico esperto: come risolvete di solito problemi simili a questo? Quali sono le strade "standard" per questa classe di problemi? Non credo proprio che questa sia l'unica percorribile...mi spiego?

[Silver87]

Ho capito , Purtroppo le strade "standard" non le conosco... speriamo che qualcuno più esperto posti qualche indicazione interessante.

Riguardo la dimostrazione per i 100 punti, credo che un ragionamento logico come quello che ho scritto, vada bene, nel senso che è accettabile come dimostrazione, però forse mi sbaglio... so che il rigore dei matematici a volte non si accontenta di cose semplici...

[giobimbo]

Il problema era stato affrontato assegnando un sistema di assi cartesiani al piano su cui sono disegnati i punti e studiando l'inclinazione delle rette che passano per due qualsiasi di essi, analizzando le poligonali formate dai segmenti che collegano coppie di punti e che si dividono in due tipi: "cups", ovvero poligonali a forma di U (il simbolo insiemistico di unione) e "caps" poligonali a forma di U rovesciata (il simbolo insiemistico di intersezione). Se leggete l'inglese, nel capitolo 2.8 di questo documento PDF ci sono delle dimostrazioni:

http://mspace.lib.umanitoba.ca/bitstrea ... Thesis.pdf" onclick="window.open(this.href);return false;

Per capire meglio "cups & caps" date un'occhiata pure a questi due, anche se il secondo non tratta esplicitamente del problema di Erdös-Szekeres:

http://www.ams.org/bull/2000-37-04/S027 ... 0877-6.pdf" onclick="window.open(this.href);return false;

http://iti.mff.cuni.cz/series/files/iti271.pdf" onclick="window.open(this.href);return false;


Tempo fa avevo elaborato una dimostrazione combinatoria, basata sulle palline dentro le scatole, per spiegare perché con 9 punti viene fuori per forza un pentagono convesso, solo che essendo pigro non ho scritto tutto per esteso, ma ho solo fatto degli schizzi e dei calcoli, tenendo il ragionamento dentro la testa. Se riesco a ricostruire il tutto e mi sembra accettabile come chiarezza, lo metto qua.

[fabtor]

Mmh, che macello, prima o poi non è detto che mi ci metterò a ragionarci su (bellissimo cmq il lavoro di silver87 anche se non sempre facilmente accessibile ad uno zuccone come il sottoscritto).

Tuttavia avevo una proposta a riguardo di una possibile strategia risolutiva: e se al posto di considerare solo il fatto che i tre punti non devono essere allineati considerassimo che comunque tre punti stanno su un unica circonferenza (non cambia nulla credo: è solo una considerazione in più) non si potrebbe approcciarsi al problema considerando sezioni di piano delimitate dalle circonferenze rispetto alle loro complementari?